{"ID":2880160,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.14516","arxiv_id":"2508.14516","title":"Incremental-Decremental Maximization","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.","short_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 untrans...","url_abs":"https://arxiv.org/abs/2508.14516","url_pdf":"https://arxiv.org/pdf/2508.14516v1","authors":"[\"Yann Disser\",\"Max Klimm\",\"Annette Lutz\",\"Lea Strubberg\"]","published":"2025-08-20T08:22:47Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}