Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

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

Cliff Stein - Columbia University, New York

Hallucination Helps: Energy Efficient Virtual Circuit Routing

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

Kevin Schewior - Technische Universität Berlin

Dealing with Unknown Future Jobs: Increasing the Machine Speed

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