5 papers
Incremental Submodular Maximization: Better Than Greedy
Marcin Bienkowski, Joakim Blikstad, Jarosław Byrka +3
We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of th…
Incremental-Decremental Maximization
Yann Disser, Max Klimm, Annette Lutz +1
We introduce a framework for incremental-decremental maximization that captures the gradual transformation or renewal of infrastructures. In our model, an initial solution is trans…
Valid Cuts for the Design of Potential-based Flow Networks
Pascal Börner, Max Klimm, Annette Lutz +3
The construction of a cost minimal network for flows obeying physical laws is an important problem for the design of electricity, water, hydrogen, and natural gas infrastructures.…
Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
Yann Disser, Svenja M. Griesbach, Max Klimm +1
We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously ap…
Fractionally Subadditive Maximization under an Incremental Knapsack Constraint
Yann Disser, Max Klimm, Annette Lutz +1
We consider the problem of maximizing a fractionally subadditive function under a knapsack constraint that grows over time. An incremental solution to this problem is given by an o…