## 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**

**Abstract:**

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

**Abstract:**

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**

**Abstract:**

We consider the NP-hard Generalized Bin Covering problem: We are given *m* bin types, where each bin of type *i* has profit *p*_{i} and demand *d*_{i}. There are *n* items, where item *j* has size *s*_{j}. A bin of type *i* is covered if the set of items assigned to it has total size at least the demand *d*_{i}. Then the profit of *p*_{i} is earned and the objective is to maximize the total profit. To the best of our knowledge, only the cases *p*_{i} = d_{i} = 1 (Bin Covering) and *p*_{i} = d_{i} (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.