Acta Informatica Computer Networks and Communications

Incremental–decremental maximization

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

Abstract

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.

Read at publisher →