## Invited Session Mon.1.H 3021

#### Monday, 10:30 - 12:00 h, Room: H 3021

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

### Scheduling algorithms I

**Chair: Nikhil Bansal**

**Monday, 10:30 - 10:55 h, Room: H 3021, Talk 1**

**Kirk Pruhs**

Online primal-dual for non-linear optimization with applications to speed scaling

**Coauthors: Anupam Gupta, Ravishankar Krishnaswamy**

**Abstract:**

We give a principled method to design online algorithms (for potentially non-linear problems) using a mathematical programming formulation of the problem, and also to analyze the competitiveness of the resulting algorithm using the dual program. This method can be viewed as an extension of the online primal-dual method for linear programming problems, to nonlinear programs. We show the application of this method to two online speed scaling problems: one involving scheduling jobs on a speed scalable processor so as to minimize energy plus an arbitrary sum scheduling objective, and one involving routing virtual circuit connection requests in a network of speed scalable routers so as to minimize the aggregate power or energy used by the routers. This analysis shows that competitive algorithms exist for problems that had resisted analysis using the dominant potential function approach in the speed scaling literature, and provides alternate cleaner analysis for other known results. This represents another step towards a principled design and analysis of primal-dual algorithms for online problems.

**Monday, 11:00 - 11:25 h, Room: H 3021, Talk 2**

**Ola Svensson**

On the hardness of scheduling with precedence constraints to minimize makespan

**Abstract:**

We will talk about the recently established reductions from a bipartite (and *k*-partite) ordering problem to two classical scheduling problems:

Scheduling with precedence constraints on identical machines to minimize makespan (*P|prec|C*_{max}) and scheduling with precedence constraints on related machines to minimize makespan (*Q|prec|C*_{max}).

Combining our reduction from the bipartite ordering problem with a recent result by Bansal & Khot shows that it is NP-hard to improve upon the classical 2-approximation by Graham'66 for identical machines, assuming a variant of the unique games conjecture.

For related machines, we show that if a generalized version of the bipartite (namely *k*-partite) ordering problem is hard then (*Q|prec|C*_{max}) does not admit a constant factor approximation algorithm. However, the hardness of the

*k*-partite ordering problem remains open even if we assume the unique games conjecture.

**Monday, 11:30 - 11:55 h, Room: H 3021, Talk 3**

**Cliff Stein**

How to schedule when you have to buy your energy

**Coauthor: Kirk Pruhs**

**Abstract:**

We consider a situation where jobs arrive over time at a data center,

consisting of identical speed-scalable processors.

For each job, the scheduler knows how much income is lost as a function

of how long the job is delayed.

The scheduler also knows the fixed cost of a unit of energy.

The online scheduler determines which jobs to run on which processors,

and at what speed to run the processors. The scheduler's objective is to

maximize profit, which is the income obtained from jobs minus

the energy costs. We give a (*1 + ε*)-speed *O(1)*-competitive

algorithm, and show that resource augmentation is necessary to

achieve *O(1)*-competitiveness.