Dagstuhl Seminar 11241
Design and Analysis of Randomized and Approximation Algorithms
Dagstuhl, June 13-17, 2011
M. Dyer (Leeds), U. Feige (Rehovot), A. Frieze (Pittsburgh), M. Karpinski (Bonn)
Tuesday, June 14th, 2011
| 09:00 - 09:10 | Opening |
| Chair: | Marek Karpinski |
| 09:10 - 09:40 | Johan Håstad (KTH - Stockholm) On the Usefulness of Predicates |
| 09:40 - 10:10 | Alexander Barvinok (University of Michigan) Counting Contingency Tables |
| 10:10 - 10:40 | Leslie Ann Goldberg (University of Liverpool) Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid |
| 10:40 - 11:00 | Coffee break |
| Chair: | Uriel Feige |
| 11:00 - 11:30 | Leen Stougie (CWI - Amsterdam) TSP on Cubic and Subcubic Graphs |
| 11:30 - 12:00 | Ola Svensson (KTH - Stockholm) Approximating Graphic TSP by Matchings |
| 12:15 | Lunch break |
| Chair: | Martin Dyer |
| 15:00 - 15:30 | Po-Shen Loh (CMU - Pittsburgh) Connectivity in Discrete Random Processes |
| 15:30 - 16:00 | Lars Prädel (University of Kiel) A (5/3+ε)-Approximation for Strip Packing |
| 16:00 - 16:30 | Coffee break |
| Chair: | Alan Frieze |
| 16:30 - 17:00 | Christian Sohler (TU Dortmund) Every Hyperfinite Property is Testable |
| 17:00 - 17:30 | Alexandr Andoni (Microsoft Research - Mountain View) Sublinear Algorithms via Precision Sampling |
| 18:00 | Dinner |
Wednesday, June 15th, 2011
| Chair: | Mark Jerrum |
| 09:00 - 09:30 | Thomas Hayes (University of New Mexico - Albuquerque) Lifting Markov Chains for Faster Mixing |
| 09:30 - 10:00 | Gregory Sorkin (London School of Economics) Average-Case Performance of Heuristics for Multi-Dimensional Assignment Problems |
| 10:00 - 10:30 | Michael Krivelevich (Tel Aviv University) Embedding Spanning Trees in Random Graphs near the Connectivity Threshold |
| 10:30 - 11:00 | Coffee break |
| Chair: | Michael Paterson |
| 11:00 - 11:30 | R. Ravi (CMU - Pittsburgh) Stochastic Knapsack |
| 11:30 - 12:00 | Heiko Röglin (University of Bonn) Smoothed Analysis of Multiobject Optimization |
| 12:15 | Lunch break |
| 13:30 - 17:30 | Excursion |
| 18:00 | Dinner |
| 19:30 | Open Problem Session |
| Chair: | Uriel Feige |
Thursday, June 16th, 2011
| Chair: | Leslie Ann Goldberg |
| 09:00 - 09:30 | Ravi Kannan (Microsoft Research) k-Means Algorithm Converges |
| 09:30 - 10:00 | Tobias Müller (CWI - Amsterdam) Random Geometric Graphs |
| 10:00 - 10:30 | Mark Jerrum (Queen Mary University of London) Hardness of Approximating the Tutte Polynomial of a Binary Matroid |
| 10:30 - 11:00 | Coffee break |
| Chair: | Alan Frieze |
| 11:00 - 11:30 | Edyta Szymanska (Adam Mickiewicz University - Poznan) Computational Complexity of the Hamilton Cycle Problem in Dense Hypergraphs |
| 11:30 - 12:00 | Andrzej Rucinski (Adam Mickiewicz University - Poznan) Distributed Storage Allocation via Fractional Hypergraph Matchings |
| 12:15 | Lunch break |
| Chair: | Michael Krivelevich |
| 15:00 - 15:30 | Berthold Vöcking (RWTH Aachen) Universally-Truthful Multi-Unit Auctions |
| 15:30 - 16:00 | Markus Bläser (University of Saarland) Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals |
| 16:00 - 16:30 | Coffee break |
| 18:00 | Dinner |
Friday, June 17th, 2011
| Chair: | Johan Håstad |
| 09:00 - 09:30 | Marek Karpinski (University of Bonn) Approximating Gale-Berlekamp Games and Related Optimization Problems |
| 09:30 - 10:00 | Alan Frieze (CMU - Pittsburgh) Vacant Set of a Random Walk on a Random Graph |
| 10:00 - 10:30 | Alessandro Panconesi (University of Rome "La Sapienza") Milgram Routing |
| 10:30 - 11:00 | Coffee break |
| Chair: | Ravi Kannan |
| 11:00 - 11:30 | Amin Coja-Oghlan (University of Edinburgh) The Condensation Transition in Random Hypergraph 2-Coloring |
| 11:30 - 12:00 | Eden Chlamtac (Weizmann Institute - Rehovot) Linear Index Coding via Semidefinite Programming |
End of Workshop | |
| 12:15 | Lunch |