Monday, April 25, 2016
Freie Universität Berlin
Takustr. 9
14195 Berlin
room 005
Lecture 1 - 14:15
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
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)