**Monday, July 14, 2014**

Technische Universität Berlin

Fakultät II, Institut für Mathematik

Str. des 17. Juni 136

10623 Berlin

room MA 041

** Lecture - 14:15**

*Abstract:*

In this talk, we give online and offline approximation algorithms for
energy efficient circuit routing protocols for a network of components
that are speed scalable, and that may be shutdown when idle. We will
consider both the case where the speed-scalable components are edges
and the case when they are nodes. For the case of edges, we describe
a polynomial-time offline algorithm that has a poly-log approximation
ratio. The key step of the algorithm design is a random sampling
technique that we call hallucination. The algorithm extends rather
naturally to an online algorithm. The analysis of the online algorithm
introduces a natural ``priority'' multicommodity flow problem, and
bounds the priority multicommodity flow-cut gap. We will then
explain the additional difficulty faced if the power management
components are vertices, and explain how to how to surmount this
difficulty in the offline case.

This work spans several papers and is joint with Antonios Antoniadis,
Nikhil Bansal, Sungjin Im, Ravishankar Krishnaswamy,
Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs.

** Colloquium - 16:00**

*Abstract:*

We consider the problem of online deadline scheduling with resouce augmentation. Here, an online algorithm has to preemptively schedule jobs (revealed only at their release date) with certain processing times on m machines before their respective deadlines. Parallelization is not allowed. To schedule each instance which can be feasibly scheduled in an offline setting, an online algorithm can be allowed to use higher speed, which can be viewed as shrinking the processing times by a certain factor. No tight bounds on this factor are known.

We firstly review known results, mostly from a seminal paper by C. A. Phillips, C. Stein, E. Torng, and J. Wein (STOC 1997). In particular, we argue that a speed of 1.2 is necessary for any online algorithm. We will see that rather simple policies such as Earliest Deadline First (EDF) and Least Laxity First (LLF) require a speed of at most 2-1/m. Whereas the tightness of this bound is easy to see for EDF, it remained as an open question for LLF since 1997. In this talk, we positively answer this question, i.e., for every speed less than 2-1/m, we give instances at which LLF using this speed fails. On instances with a fixed number of release dates however, LLF turns out to achieve better bounds, which partially even surpass those of any other known algorithm. In particular, LLF is shown to require only unit speed for a single release date and a speed of 4-2*sqrt(2)≈1.17 for two different release dates. We also give general lower bounds on the speed required by any online algorithm for a fixed number of release dates.

This is joint work with Nicole Megow.

Letzte Aktualisierung:
08.07.2014