Incremental–Decremental Maximization

Yann Disser, Max Klimm, Annette Lutz, Lea Strubberg · 2025

Read Incremental–Decremental Maximization by Yann Disser, Max Klimm, Annette Lutz, Lea Strubberg (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-14516.txt.

Introduction

Yann Disser and co-authors introduced this 2025 framework for renewing systems one piece at a time. Think of upgrading a network or a fleet: an old setup is swapped element by element toward a new one. At each stage, the value mixes the worth of the new parts already in and the old parts still running. The authors ask how to order the swaps so value stays high throughout.

They give a coin-flip method and a fixed-rule method that both keep stages competitive with the best plan for that stage. The guarantees hold for value functions with bounded bend, including the common submodular kind. The paper also shows this joint problem is much harder than the one-way version, where nothing is removed.

Catalog record

CREATORYann Disser, Max Klimm, Annette Lutz, Lea Strubberg
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-14516

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Incremental–Decremental Maximization Yann Disser, Max Klimm, Annette Lutz, Lea Strubberg 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 and a deterministic algorithm that both find an order in which to transform the elements while maintaining a large utility during all stages of transformation, relative to an optimum 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 gross substitute functions. Our results exhibit that incremental–decremental maximization is substantially more difficult than incremental maximization. TU Darmstadt, [email protected]://orcid.org/0000-0002-2085-0454 TU Berlin, [email protected]://orcid.org/0000-0002-9061-2267 TU Darmstadt, [email protected]://orcid.org/0009-0008-7699-7018 TU Berlin, [email protected]://orcid.org/0009-0009-8505-3614 We are grateful to Martin Knaack, Jannik Matuschke, and David Weckbecker for helpful discussions on functions of bounded curvature, gross substitute functions and incremental maximization, respectively. We also thank Júlia Baligács and Nils Mosis for an initial exchange about the topic. ccs Theory of computation Online algorithms ccs Mathematics of computing Combinatorial algorithms ccs Mathematics of computing Combinatorial optimization keywords incremental optimization, competitive analysis, submodular function, gross substitute function † † runningauthor: Y. Disser, M. Klimm, A. Lutz, L. Strubberg † † copyright: Yann Disser, Max Klimm, Annette Lutz and Lea Strubberg † † funding: Supported by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) through subprojects A07 and A09 of CRC/TRR154. 1 Introduction Incremental maximization provides a mathematical model to study situations where a new infrastructure is constructed over time. The infrastructure consists of a set of elements E . The benefit for having built a subset of elements is defined by a set function f\colon 2^{E}\to\mathbb{R}_{\geq 0} that maps each partial solution S\subseteq E to its benefit f(S) . Depending on the application, the elements may model, e.g., pipes of a pipe system, wires in an electric network, or machines in a workshop. The benefit f(S) models, e.g., averaged annual returns from operating the partial infrastructure S . Given such a situation, it is a natural question in which order the elements should be constructed. This question is addressed with the theory of incremental maximization problems. Formally, an incremental solution is an order \pi=(e_{1},\dots,e_{n}) of the elements of E where n=|E| . The quality of an incremental solution is measured by a competitive analysis. To this end, for k\in\{1,\dots,n\} , let \textrm{OPT}_{k}\coloneqq\max\bigl\{f(S):S\subseteq E\text{ with }|S|=k\bigr\} be the value of an optimal solution with k elements. For an incremental solution \pi=(e_{1},\dots,e_{n}) and k\in\{1,\dots,n\} , let S_{k}\coloneqq\{e_{1},\dots,e_{k}\} denote the prefix of the first k elements of \pi . Then, the competitive ratio of an incremental solution \pi is defined as \rho\coloneqq\inf\bigl\{r\in\mathbb{R}_{\geq 0}:r\,f(S_{k})\geq\textrm{OPT}_{k}\text{ for all }k\in\{1,\dots,n\}\bigr\} , and one is interested in finding incremental solutions with a low competitive ratio. In this framework, upper and lower bounds on the best-possible competitive ratio have been derived for various classes of set functions f [ 1 , 7 , 8 , 9 ] . While the incremental maximization framework is a suitable model for situations where a new infrastructure needs to be constructed from scratch, it fails to capture scenarios where an existing infrastructure is upgraded to a new technological standard. As an example, suppose that E is a set of cell phone towers, and let g(S) be the total amount of data transferrable with a subset S\subseteq E of the towers using an old technological standard. The technology of the cell phone towers is to be updated to a new and non-interoperable standard; let h(S) be the total amount of data transferable with a subset S\subseteq E of the towers using the new standard. 1 1 1 In a similar vein, one may consider a pipeline network being upgraded from operation with natural gas ( g ) to operation with hydrogen ( h ); this is our motivation to use g for the function evaluating the benefit from the old standard and h for the function evaluating the benefit from the new standard. In this context it is natural to ask in which order the cell towers should be upgraded in order to ensure that the amount of data transferrable in total across both standards is high at every point in time. To phrase and answer this question formally, in this paper, we introduce a novel incremental–decremental optimization framework that generalizes incremental maximization. In analogy to the incremental maximization framework, we call an ordering \pi=(e_{1},\dots,e_{n}) of the elements an incremental–decremental solution. Such an order increments the set of elements using the new technology while decrementing the set of elements using the old technology, hence the name. For two arbitrary set functions h,g\colon 2^{E}\to\mathbb{R}_{\geq 0} , let f\colon 2^{E}\to\mathbb{R}_{\geq 0} be defined as f(S)\coloneqq h(S)+g(E\setminus S) . Note that in the application above f(S) is equal to the total amount of data transferable using both standards whence the subset S\subseteq E of cell phone towers has been upgraded. As before, let \textrm{OPT}_{k}\coloneqq\max\bigl\{f(S):S\subseteq E\text{ with }|S|=k\bigr\} . The competitive ratio of the incremental–decremental solution \pi is then defined as \displaystyle\rho\coloneqq\inf\bigl\{r\in\mathbb{R}_{\geq 0}:rf(S_{k})\geq\textrm{OPT}_{k}\text{ for all }k\in\{1,\dots,n\}\bigr\}. The competitive ratio of an algorithm is the supremum over the competitive ratios of its solutions. Likewise the competitive ratio of a problem is the infinum over the competitive ratios of an algorithm for the problem. We say that an algorithm or a solution is \rho - competitive if its competitive ratio is at most \rho . Since the notions of an incremental–decremental solution for h and g , and that of an incremental solution for f defined by f(S)=h(S)+g(E\setminus S) coincide, one may wonder why it is insightful to introduce incremental–decremental solutions in the first place. The reason for this stems from the fact that the incremental–decremental framework allows to impose natural properties of the functions h and g that may not be phrased so conveniently for the combined function f . For instance, in the above example of upgrading the technology of cell phone towers, it is natural to assume that both the function h and g are monotone. However, f(S)=h(S)+g(E\setminus S) is then generally non-monotone and thus known results for incremental maximization (that all require monotonicity) do not apply. As a consequence, we will see that the best-possible competitive ratio in the incremental–decremental setting is strictly worse than in the incremental setting for monotone submodular functions. A general treatment of the incremental maximization problem with non-monotone objective function f however does not yield meaningful results as it is unbounded even if f is submodular; see Proposition 23 in Section A.1 . 1.1 Our Results We give polynomial-time algorithms computing an incremental–decremental solution whose performances are parametrized by the generic submodularity ratio \gamma\in(0,1] and the curvature c\in(0,1] of the functions g and h ; these properties of set functions are formally defined in Definitions 6 and 7 . As a warm-up, we examine a simple randomized algorithm that takes uniformly at random the greedy order of the elements in E regarding h or the reverse greedy order with respect to g . For this randomized algorithm, an upper

Read the complete text