@unpublished{DisserKlimmWeckbecker2021, author = {Disser, Yann and Klimm, Max and Weckbecker, David}, title = {Fractionally Subadditive Maximization under an Incremental Knapsack Constraint}, year = {2021}, abstract = {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.}, language = {en} } @article{AbedChenDisseretal.2017, author = {Abed, Fidaa and Chen, Lin and Disser, Yann and Groß, Martin and Megow, Nicole and Meißner, Julie and Richter, Alexander T. and Rischke, Roman}, title = {Scheduling Maintenance Jobs in Networks}, year = {2017}, abstract = {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.}, language = {en} } @article{BernsteinDisserGross2017, author = {Bernstein, Aaron and Disser, Yann and Groß, Martin}, title = {General Bounds for Incremental Maximization}, year = {2017}, abstract = {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.}, language = {en} }