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


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


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|Cmax) and scheduling with precedence constraints on related machines to minimize makespan (Q|prec|Cmax).
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|Cmax) 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


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.


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra Without Prescription influence on blood clots.