caa a22 4500 467989753 CHVBK 20180323112541.0 cr unu---uuuuu 170328e19900701xx s 000 0 eng 10.1007/BF00259471 doi (NATIONALLICENCE)springer-10.1007/BF00259471 Proving relative lower bounds for incremental algorithms [Elektronische Daten] [A. Berman, Marvin Paull, Barbara Ryder] Summary: A general method that permits simple proofs of relative lower bounds for incremental update algorithms is presented. This method is applied to classify 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 [PCB] and generalizes a result of Even and Gazit [EG]. Our results have interesting implications with respect to the optimality of an incremental algorithm previously developed by Ryder in [R, RP2]. Perhaps most importantly, the proof method and function classification 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. Springer-Verlag, 1990 Berman A. Department of Computer Science, Rutgers University, 08903, New Brunswick, NJ, USA aut Paull Marvin Department of Computer Science, Rutgers University, 08903, New Brunswick, NJ, USA aut Ryder Barbara Department of Computer Science, Rutgers University, 08903, New Brunswick, NJ, USA aut Acta Informatica Springer-Verlag 27/7(1990-07-01), 665-683 0001-5903 27:7<665 1990 27 236 https://doi.org/10.1007/BF00259471 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00259471 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Berman A. Department of Computer Science, Rutgers University, 08903, New Brunswick, NJ, USA aut NATIONALLICENCE 700 1- Paull Marvin Department of Computer Science, Rutgers University, 08903, New Brunswick, NJ, USA aut NATIONALLICENCE 700 1- Ryder Barbara Department of Computer Science, Rutgers University, 08903, New Brunswick, NJ, USA aut NATIONALLICENCE 773 0- Acta Informatica Springer-Verlag 27/7(1990-07-01), 665-683 0001-5903 27:7<665 1990 27 236 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer