Dagstuhl Seminar 08201
Design and Analysis of Randomized and Approximation Algorithms
Dagstuhl, May 11-16, 2008
M. Dyer (Leeds), M. Jerrum (London), M. Karpinski (Bonn)
Monday, May 12th, 2008
| 09:00 - 09:10 | Opening |
| Chair: | Marek Karpinski |
| 09:10 - 09:40 | Alan Frieze (CMU - Pittsburgh) Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time |
| 09:40 - 10:10 | Alexander Barvinok (University of Michigan) Counting contingency tables and integer flows |
| 10:10 - 10:40 | Alex D. Scott (Oxford University) Triangles in random graphs |
| 10:40 - 11:00 | Coffee break |
| Chair: | Mark Jerrum |
| 11:00 - 11:30 | Michael Langberg (The Open Univ. of Israel - Raanan) Two subgraph maximization problems |
| 11:30 - 12:00 | Zoya Svitkina (Dartmouth College - Hanover) Sampling-based algorithms for submodular approximation |
| 12:15 | Lunch break |
| Chair: | Martin Dyer |
| 15:00 - 15:30 | Catherine Greenhill (Univ. of New South Wales) The cycle structure of two rows in a random latin square |
| 15:30 - 16:00 | Colin Cooper (King's College - London) Multiple random walks on random regular graphs |
| 16:00 - 16:30 | Coffee break |
| 18:00 | Dinner |
Tuesday, May 13th, 2008
| Chair: | Alan Frieze |
| 09:00 - 09:30 | Mark Jerrum (Queen Mary College - London) An Approximation Trichotomy for Boolean #CSP |
| 09:30 - 10:00 | Leslie Ann Goldberg (University of Liverpool) A complexity dichotomy for partition functions with mixed signs |
| 10:00 - 10:30 | Dimitris Achlioptas (Univ. California - Santa Cruz) Algorithmic Phase Transitions in Random Constraint Satisfaction Problems |
| 10:30 - 11:00 | Coffee break |
| Chair: | Michael Paterson |
| 11:00 - 11:30 | Christoph Dürr (CNRS, Ecole Polytechnique - Palaiseau) Nash equilibria in Voronoi games on graphs |
| 11:30 - 12:00 | Ingo Wegener (Technische Universität Dortmund) Tight Bounds for Blind Search on the Integers |
| 12:15 | Lunch break |
| Chair: | Dorit Hochbaum |
| 15:00 - 15:30 | Thomas Hayes (Toyota Technological Institute) The Forgiving Tree |
| 15:30 - 16:00 | Markus Jalsenius (University of Liverpool) A systematic scan for 7-colourings of the grid |
| 16:00 - 16:30 | Coffee break |
| 18:00 | Dinner |
Wednesday, May 14th, 2008
| Chair: | Moni Naor |
| 09:00 - 09:30 | Uriel Feige (Weizmann Inst. - Rehovot) Structural Approximations: A Framework for Analyzing and Designing Heuristics |
| 09:30 - 10:00 | Bernd Gärtner (ETH Zürich) Rational Unique Sink Orientations |
| 10:00 - 10:30 | Alantha L. Newman (RWTH Aachen) Linear Equations mod p |
| 10:30 - 11:00 | Coffee break |
| Chair: | Alexander Barvinok |
| 11:00 - 11:30 | Dorit S. Hochbaum (Univ. California - Berkeley) Cut-based algorithms for image segmentation |
| 11:30 - 12:00 | Andrzej Lingas (Lund University) Efficient approximation algorithms for shortest cycles in undirected graphs |
| 12:15 | Lunch break |
| 13:30 - 17:30 | Excursion |
| 18:00 | Dinner |
| 19:30 | Open Problem Session |
| Chair: | Uriel Feige |
Thursday, May 15th, 2008
| Chair: | Uriel Feige |
| 09:00 - 09:30 | Marek Karpinski (University of Bonn) Sample Complexity of Nondense MAX-CUT |
| 09:30 - 10:00 | Moni Naor (Weizmann Inst. - Rehovot) An Optimally Fair Coin Toss: Cleve’s Bound is Tight |
| 10:00 - 10:30 | Konstantinos Panagiotou (ETH Zürich) Maximum Cuts and Other Extremal Subgraphs of Random Graphs |
| 10:30 - 11:00 | Coffee break |
| Chair: | Peter Gritzmann |
| 11:00 - 11:30 | Christian Sohler (University of Bonn) Clustering for Metric and Non-Metric Distance Measures |
| 11:30 - 12:00 | Leen Stougie (TU Eindhoven) Data gathering in wireless communication networks |
| 12:15 | Lunch break |
| Chair: | Artur Czumaj |
| 15:00 - 15:30 | Ola Svensson (IDSIA - Lugano) (Acyclic) Job Shops are Hard to Approximate |
| 15:30 - 16:00 | Markus Bläser (Saarland University) Randomness optimal identity tests of blackbox polynomials |
| 16:00 - 16:30 | Coffee break |
| 18:00 | Dinner |
Friday, May 16th, 2008
| Chair: | Moni Naor |
| 09:00 - 09:30 | Martin E. Dyer (University of Leeds) Randomly colouring random graphs |
| 09:30 - 10:00 | Magnus Bordewich (University of Durham) Path coupling without contraction |
| 10:00 - 10:30 | Amin Coja-Oghlan (University of Edinburgh) Quasi-random graphs: eigenvalues and discrepancy |
| 10:30 - 11:00 | Coffee break |
| Chair: | Leslie Ann Goldberg |
| 11:00 - 11:30 | Peter Gritzmann (TU München) Optimal Wire Ordering and Spacing in Low Power Semiconductor Design |
End of Workshop | |
| 12:15 | Lunch |