## Invited Session Mon.2.H 3021

#### Monday, 13:15 - 14:45 h, Room: H 3021

**Cluster 2: Combinatorial optimization** [...]

### Scheduling algorithms II

**Chair: Vincenzo Bonifaci**

**Monday, 13:15 - 13:40 h, Room: H 3021, Talk 1**

**Cyriel Rutten**

Scheduling sporadic tasks on unrelated parallel machines

**Coauthors: Alberto Marchetti-Spaccamela, Suzanne van der Ster, Andreas Wiese**

**Abstract:**

In modern hardware architectures it has become a very common feature to contain several types of processors with possibly completely different characteristics. In (real-time) scheduling, this feature is modeled by assuming the machines of a system to be unrelated. We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled.

We develop a polynomial-time algorithm which approximates the problem with a constant speedup factor of *11+4 √3 ≈ 17.9* when the number of machines is arbitrary. Further, we show that any polynomial-time algorithm needs a speedup factor of at least *2*, unless P = NP. Also, if the number of machines is constant, we approximate the problem to a factor of *1+ ε*. Key to these results are two new relaxations of the demand bound function which yields a sufficient and necessary condition for a task system on a single machine to be feasible.

**Monday, 13:45 - 14:10 h, Room: H 3021, Talk 2**

**Andreas Wiese**

A new approach to online scheduling: Approximating the optimal competitive ratio

**Coauthors: Elisabeth Günther, Olaf Maurer, Nicole Megow**

**Abstract:**

We propose a new approach to competitive analysis in online scheduling by introducing the concept of online approximation schemes. Such a scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. Also, it provides algorithmic means to compute the actual value of the best possible competitive ratio up to an arbitrary accuracy.

We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines. By constructing online approximation schemes we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. We also generalize our techniques to arbitrary monomial cost functions and apply them to the makespan objective. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations.

**Monday, 14:15 - 14:40 h, Room: H 3021, Talk 3**

**Nicole Megow**

Nearly optimal universal solutions for knapsack and sequencing on an unreliable machine

**Coauthor: Julian Mestre**

**Abstract:**

Dual-value sequencing with an unknown covering or packing constraint appears as a core subproblem, e.g., when scheduling on an unreliable machine or when determining a universal knapsack solution. A sequence is called *α*-robust when, for any possible constraint, the maximal or minimal prefix of the sequence that satisfies the constraint is at most a factor *α* from an optimal packing or covering. It is known that the covering problem always admits a 4-robust solution, and there are instances for which this factor is tight. For the packing variant no such constant robustness factor is possible.

In this work we aim for more meaningful, instance-dependent robustness guarantees. We present an algorithm that constructs for each instance a solution with a robustness factor arbitrarily close to optimal. This implies nearly optimal solutions for universal knapsack and scheduling on an unreliable machine. The crucial ingredient is an approximate feasibility test for dual-value sequencing with a given target function. This result may be of independent interest. We show that deciding exact feasibility is strongly NP-hard, and thus, our test is best possible, unless P=NP.