TY - INPR A1 - Disser, Yann A1 - Klimm, Max A1 - Weckbecker, David T1 - Fractionally Subadditive Maximization under an Incremental Knapsack Constraint N2 - 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 order in which to include the elements of the ground set, and the competitive ratio of an incremental solution is defined by the worst ratio over all capacities relative to an optimum solution of the corresponding capacity. We present an algorithm that finds an incremental solution of competitive ratio at most $\max\{3.293\sqrt{M},2M\}$, under the assumption that the values of singleton sets are in the range $[1,M]$, and we give a lower bound of $\max\{2.449,M\}$ on the attainable competitive ratio. In addition, we establish that our framework captures potential-based flows between two vertices, and we give a tight bound of 2 for the incremental maximization of classical flows with unit capacities. Y1 - 2021 ER - TY - CHAP A1 - Disser, Yann A1 - Griesbach, Svenja M. A1 - Klimm, Max A1 - Lutz, Annette T1 - Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem N2 - 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 approximates the optimum for all budgets, we show that a bicriterial (α,μ)-approximation is possible, i.e., a solution that with budget B+α for all B∈R≥0 is a multiplicative μ-approximation compared to the optimum solution with budget B. For the case that the underlying graph is a tree, we present a polynomial-time density-greedy algorithm that computes a (χ,1)-approximation, where χ denotes the eccentricity of the root vertex in the underlying graph, and show that this is best possible. An adaptation of the density-greedy algorithm for general graphs is (γ,2)-competitive where γ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm does not run in polynomial time, it can be adapted to a (γ,3)-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a (3χ,8)-approximation and, more generally, a ((4ℓ−1)χ,(2^(ℓ+2))/(2^ℓ−1))-approximation for every fixed ℓ∈N. KW - incremental maximization KW - competitive analysis KW - prize-collecting Steiner-tree Y1 - 2024 ER - TY - INPR A1 - Strubberg, Lea A1 - Lutz, Annette A1 - Börner, Pascal A1 - Pfetsch, Marc A1 - Skutella, Martin A1 - Klimm, Max T1 - Valid Cuts for the Design of Potential-based Flow Networks N2 - 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. We formulate this problem as a mixed-integer non-linear program. Its non-convexity, due to the poten- tial flow, together with the binary variables, indicating the decision to build a connection, make these problems challenging to solve. We develop a novel class of valid inequalities on the fractional relaxations of the bi- nary variables. Further, we show that this class of inequalities can be sep- arated in polynomial for solutions to a fractional relaxation. This makes it possible to incorporate these inequalities into a branch-and-bound al- gorithm. The advantage of these inequalities is lastly demonstrated in a computational study on the design of real-world gas transport networks. KW - potential based flows KW - topology optimization KW - MINLP Y1 - 2025 ER -