Proving Relative Lower Bounds for Incremental Algorithms

A general powerful method that permits simple proofs of relative lower bounds for incremental update algorithms is presented. This method is applied to derive a hierarchy of relative incremental complexity. Which classifies functions by relative lower bounds. We demonstrate our technique by bounding a number of incremental algorithms drawn from various domains. The method described expands upon work by Paull, Berman, and Cheng ~71 and generalizes a result of Even and Gazit 2. Our results have interesting implications with respect to the optimality of an incremental algorithm previously developed by Ryder in [9, 101. We also show that for certain graphs, Frederickson's update algorithm for minimum spanning tree is nearly optimal. Perhaps most importantly, the proof method and hierarchy suggest which types of problems are likely to yield good incremental algorithms (i.e., of lower complexity) and which cannot be improved by an incremental approach.Technical report DCS-TR-15