Invited Session Thu.2.H 3010

Thursday, 13:15 - 14:45 h, Room: H 3010

Cluster 1: Approximation & online algorithms [...]

Scheduling, packing and covering


Chair: Nicole Megow



Thursday, 13:15 - 13:40 h, Room: H 3010, Talk 1

Wiebke Höhn
On the performance of Smith's rule in single-machine scheduling with nonlinear cost

Coauthor: Tobias Jacobs


We consider the problem of scheduling jobs on a single machine.
Given some continuous cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each individual job is determined by the cost function value at the job's completion time. This problem is closely related to scheduling a single machine with nonuniform processing speed. We show that for piecewise linear cost functions it is strongly NP-hard.
The main contribution of this article is a tight analysis of the approximation factor of Smith's rule under any particular convex or concave cost function. More specifically, for these wide classes of cost functions we reduce the task of determining a worst case problem instance to a continuous optimization problem, which can be solved by standard algebraic or numerical methods. For polynomial cost functions with positive coefficients it turns out that the tight approximation ratio can be calculated as the root of a univariate polynomial.
To overcome unrealistic worst case instances, we also give tight bounds that are parameterized by the minimum, maximum, and total processing time.



Thursday, 13:45 - 14:10 h, Room: H 3010, Talk 2

Christoph Dürr
Packing and covering problems on the line as shortest path problems


A popular approach to understand a new problem is to model it as an integer linear program, and to analyze properties of the relaxed linear program. Sometimes one might discover the the variable-constraint matrix is totally unimodular (TUM), which implies that the problem has a polynomial time solution, most likely with a flow structure. In some cases however the linear program is not TUM, but nevertheless has the property, that whenever it has a solution, all optimal extrem point solutions are integral. Again this leads to a polynomial time solution, just by solving the relaxed linear program. D. and Mathilde Hurand in 2006 found that some of these linear programs could be simplified as shortest path formulations. In 2011 Alejandro L\'{o}pez-Ortiz and Claude-Guy Quimper showed how the special structure of these shortest path instances could be used to solve the problem within improved running time. In this talk the outline of these analysis and simplification techniques are presented, illustrated on packing and covering problems on the line.



Thursday, 14:15 - 14:40 h, Room: H 3010, Talk 3

Alexander Souza
Approximation algorithms for generalized and variable-sized bin covering

Coauthor: Matthias Hellwig


We consider the NP-hard Generalized Bin Covering problem: We are given m bin types, where each bin of type i has profit pi and demand di. There are n items, where item j has size sj. A bin of type i is covered if the set of items assigned to it has total size at least the demand di. Then the profit of pi is earned and the objective is to maximize the total profit. To the best of our knowledge, only the cases pi = di = 1 (Bin Covering) and pi = di (Variable-Sized Bin Covering) have been treated before. We study two models of bin supply: In the unit supply model, we have exactly one bin of each type and in the infinite supply model, we have arbitrarily many bins of each type.
We prove that there is a combinatorial 5-approximation algorithm for Generalized Bin Covering with unit supply, which has running time O(nm√m+n). For Variable-Sized Bin Covering, we show that the Next Fit Decreasing (NFD) algorithm is a 9/4-approximation in the unit supply model. We also show that there is an AFPTAS for Variable-Sized Bin Covering in the infinite supply model.


  There are three major facts that should be watched out for in all payday loans in the United States. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.