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
partners


Monday Lecture and Colloquium


Monday, April 25, 2016

Freie Universität Berlin
Takustr. 9
14195 Berlin
room 005



Lecture 1 - 14:15

Dhruv Mubayi - University of Illinois at Chicago

New developments in Ramsey theory

Abstract:
I will describe several new constructions in hypergraph Ramsey theory. These constructions settle old conjectures of Erdős-Hajnal (1972) on classical Ramsey numbers and Ajtai-Erdős-Komlós-Szeméredi (1981) on off-diagonal variants, as well as more recent questions due to Conlon-Fox-Lee-Sudakov and others on generalized Ramsey problems. The talk will be accessible to a general combinatorial/mathematical audience.




Lecture 2 - 16:00

Leen Stougie - Vrije Universiteit Amsterdam

Minimizing maximum and average makespan scheduling over scenarios:
a study of complexity changes due to scenarios

Abstract:
Scenarios are basic ingredients of optimization problems under uncertainty. Usually, they are specified only implicitly, e.g. as ranges over parameter values. Together with a distribution function over the scenarios, they lead to stochastic optimization problems. A classical model here is the stochastic linear optimization problem. In this model, if scenarios are specified completely and individually, then the problem can be formulated as an LP problem, blown up with the scenarios. The problem remain polynomially solvable.

We wish to investigate if this is a common phenomenon or if complexity of problems can change if scenarios are introduced into a problem. We do so at the hand of studying, most prominently, the basic 2-machine makespan scheduling problem. In this problem we are given a set J of jobs, each with its processing time, and a set of k scenarios, where each scenario is specified as a subset of jobs in J that must be executed if that scenario occurs. The goal is to find an assignment of jobs to the two machines that is the same for all scenarios. We consider two objectives: minimizing the maximum makespan over all scenarios (robust version) and minimizing the average of makespans of all scenarios (stochastic version).

We show that the presence of scenarios increases the complexity of the problem significantly. As a dramatic example, I mention the ordinary, single scenario, version of the problem with all processing times equal to 1, which is a trivial problem. With scenarios the robust version of the problem becomes inapproximable within ratio 2 unless P=NP. This is even more surprising once one realizes that putting al jobs on one machine already yields a 2-approximation.

In the makespan scheduling problem on 2 machines all leaps in complexity require that the number of scenarios is part of the input. If time permits I will give an example of a scheduling problem that is in P in its ordinary version and becomes NP-hard already for 3 scenarios. These results mostly show the mysterious role that scenarios play in the complexity of combinatorial optimization problems.

This is based on work in collaboration with Martin Dyer (UL), Esteban Feuerstein (UBA), Alberto Marchetti-Spaccamela (LSUR), Frans Schalekamp (Cornell), Rene Sitters (VU/CWI), Suzanne van der Ster (TUM), Anke van Zuylen (CMW)



Letzte Aktualisierung: 20.04.2016