When and where

When: October 13, 2008. 11:00-17:00.
Where: Diamant Seminar Room, HG 9.41 (11:00-15:00) and Auditorium (16:00-17:00) Technische Universiteit Eindhoven.

The route and a campus map can be found here.

11:00-11:45	David B. Shmoys (Cornell University)   Primal-dual schema for capacitated covering problems. Abstract. Primal-dual algorithms have played an integral role in recent developments in approximation algorithms, and yet there has been little work on these algorithms in the context of LP relaxations that have been strengthened by the addition of more sophisticated valid inequalities. We introduce primal-dual schema based on the LP relaxations devised by Carr, Fleischer, Leung & Phillips for the minimum knapsack problem as well as for the single-demand capacitated facility location problem. Our primal-dual algorithms achieve the same performance guarantees as the LP-rounding algorithms of Carr et al., which rely on applying the ellipsoid algorithm to an exponentially-sized LP. Furthermore, we introduce new knapsack-cover inequalities to strengthen the LP relaxation of the more general capacitated single-item lot-sizing problem; using just these inequalities as the LP relaxation, we obtain a primal-dual algorithm that finds solutions of cost guaranteed to be within a factor of 2 of optimal.
11:45-13:15	Lunch at Kennispoort Everybody who wishes to participate in the lunch is asked to register by sending an email to Jarek Byrka before Thursday, October 9, at 12:00 noon.
13:15-14:00	Krzysztof Apt (Centrum Wiskunde en Informatica, en Universiteit van Amsterdam)   Socially optimal mechanisms. Abstract. The purpose of mechanism design, sometimes called reverse game theory, is to align agents' preferences so that the decision taken by the central authority is beneficial for the society. A natural objective is to look for solutions that generate maximal social welfare. So in the case of a single item auction we would not aim at maximizing seller's utility but at minimizing it, which corresponds to determining at the least social cost who values the item most. We discuss our recent results concerning maximizing social welfare in simultaneous and in sequential mechanisms. They are concerned with the single item auction and the public project problem. (Based on works with V. Conitzer, A. Estevez-Fernandez, V. Markakis and M. Guo).
14:15-15:00	Mark de Berg (Technische Universiteit Eindhoven)   Computational Geometry for Fat Objects and Low Density Scenes. Abstract. Traditional worst-case analysis of geometric algorithms often fails to predict their performance in practice, because the worst-case running time only arises for very contrived inputs. As a result, practically efficient algorithms are sometimes discarded because their worst-case performance is bad. This has lead to research into the design and analysis of geometric algorithms for so-called realistic input models, in particular algorithms for fat objects and low density scenes. In this talk I will survey some of the results that have been obtained in this area.
15:00-16:00	Break
16:00-17:00	PhD Defense of Jarek Byrka Auditorium of TU Eindhoven   Randomized Approximation Algorithms: Facility Location, Phylogenetic Networks, Nash Equilibria.
17:00-18:00	Reception

There is no registration fee, but everybody interested in participating in the lunch is kindly asked to send an email to Jarek Byrka before Thursday, October 9, at 12:00 noon.

All further questions to: Karen Aardal or Jarek Byrka