Graduiertenkolleg: Methods for Discrete Structures

Monday, January 31, 2011

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin

room MA 041

Lecture - 14:15

Volker Kaibel - Magdeburg

Projections in Combinatorial Optimization

Abstract:
The polytopes associated with combinatorial optimization problems can have quite a complicated facet structure, even for problems that can be solved in polynomial time. In many cases, however, one can obtain such polytopes as projections of much simpler polyhedra, whose linear descriptions then are called extended formulations. In the first part of the lecture we will discuss some examples and tools for constructing extended formulations, while in the second part the question of fundamental limits of the approach is addressed. In contrast to a conjecture of Yannakakis (1991), we show that the minimal sizes of extended formulations of certain matching and cycle polytopes for complete graphs severely depend on whether one imposes symmetry requirements or not. The talk is based on joint work with Andreas Loos, Kanstantsin Pashkovich, and Dirk O. Theis.

Colloquium - 16:00

Andreas Wiese - Berlin

Scheduling on unrelated machines: limits of LP-approaches
(joint work with Jose Verschae)

Abstract:
We study the problem of scheduling a given set of jobs on unrelated machines. For minimizing the makespan the best known approximation algorithm for this problem guarantees an approximation factor of 2. It is known to be NP-hard to approximate the problem with a better ratio than 3/2. Closing this gap has been open for 20 years and it was listed in "Polynomial time approximation algorithms for machine scheduling: Ten open problems" by Schuurman and Woeginger.
All known approaches to approximate this problem are based on a natural LP- relaxation which has variables assigning jobs to machines. We explain why it is so difficult to add additional cuts that help diminishing the integrality gap. We prove this by showing that the Configuration-LP -- which implicitly contains a vast class of inequalities for the natural LP -- has an integrality gap of 2. This holds even for the very special case that every job can be processed on at most two machines.
Then we turn to another objective function: maximize the minimum machine load. This can be seen as allocating items to agents in order to maximize fairness. For the case that every job/item can be assigned to at most two machines/agents we give a purely combinatorial 2-approximation which is best possible, unless P=NP.

• entire schedule - WS 2010-2011