Acta Informatica Компьютерные сети и коммуникации

Incremental–decremental maximization

Yann Disser, Max Klimm, Annette Lutz, Lea Strubberg
Springer Nature · 2026-08-14 · DOI 10.1007/s00236-026-00546-x

Аннотация

Abstract We introduce a framework for incremental–decremental maximization that captures the gradual transformation or renewal of infrastructures. In our model, an initial solution is transformed one element at a time and the utility of an intermediate solution is given by the sum of the utilities of the transformed and untransformed parts. We propose a simple randomized algorithm and a more sophisticated deterministic algorithm, both of which find an order in which to transform the elements while maintaining a large utility during all stages of transformation, relative to an optimal solution for the current stage. More specifically, our algorithms yield competitive solutions for utility functions of bounded curvature and/or generic submodularity ratio, and, in particular, for submodular functions and functions satisfying the gross substitutes property. Our results show that incremental–decremental maximization is substantially more difficult than incremental maximization.

Читать у издателя →