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 - JOUR A1 - Abed, Fidaa A1 - Chen, Lin A1 - Disser, Yann A1 - Groß, Martin A1 - Megow, Nicole A1 - Meißner, Julie A1 - Richter, Alexander T. A1 - Rischke, Roman T1 - Scheduling Maintenance Jobs in Networks N2 - We investigate the problem of scheduling the maintenance of edges in a network, motivated by the goal of minimizing outages in transportation or telecommunication networks. We focus on maintaining connectivity between two nodes over time; for the special case of path networks, this is related to the problem of minimizing the busy time of machines. We show that the problem can be solved in polynomial time in arbitrary networks if preemption is allowed. If preemption is restricted to integral time points, the problem is NP-hard and in the non-preemptive case we give strong non-approximability results. Furthermore, we give tight bounds on the power of preemption, that is, the maximum ratio of the values of non-preemptive and preemptive optimal solutions. Interestingly, the preemptive and the non-preemptive problem can be solved efficiently on paths, whereas we show that mixing both leads to a weakly NP-hard problem that allows for a simple 2-approximation. Y1 - 2017 ER - TY - JOUR A1 - Bernstein, Aaron A1 - Disser, Yann A1 - Groß, Martin T1 - General Bounds for Incremental Maximization N2 - We propose a theoretical framework to capture incremental s olutions to cardinality con- strained maximization problems. The defining characterist ic of our framework is that the cardinality/support of the solution is bounded by a value k ∈ N that grows over time, and we allow the solution to be extended one element at a time. We i nvestigate the best-possible competitive ratio of such an incremental solution, i.e., th e worst ratio over all k between the incremental solution after k steps and an optimum solution of cardinality k . We define a large class of problems that contains many important cardin ality constrained maximization problems like maximum matching, knapsack, and packing/cov ering problems. We provide a general 2 . 618-competitive incremental algorithm for this class of pr oblems, and show that no algorithm can have competitive ratio below 2 . 18 in general. In the second part of the paper, we focus on the inherently inc remental greedy algorithm that increases the objective value as much as possible in eac h step. This algorithm is known to be 1 . 58-competitive for submodular objective functions, but it has unbounded competitive ratio for the class of incremental problems mentioned above . We define a relaxed submod- ularity condition for the objective function, capturing pr oblems like maximum (weighted) ( b -)matching and a variant of the maximum flow problem. We show t hat the greedy algo- rithm has competitive ratio (exactly) 2 . 313 for the class of problems that satisfy this relaxed submodularity condition. Note that our upper bounds on the competitive ratios transla te to approximation ratios for the underlying cardinality constrained problems. Y1 - 2017 ER -