Dagstuhl Seminar 01231
Design and Analysis of Randomized and Approximation Algorithms
Dagstuhl, June 6-8, 2001
M. Dyer (Leeds), M. Jerrum (Edinburgh), M. Karpinski (Bonn)
Monday, June 4th, 2001
| 09:00 - 09:10 | Opening |
| Chair: | Marek Karpinski |
| 09:10 - 09:55 | Sanjeev Khanna (PennUniv.) Algorithms for Minimizing Weighted Flow Time |
| 09:55 - 10:25 | Alan Frieze (CMU) Edge Disjoint Paths in Expander Diagraphs |
| 10:25 - 11:00 | Coffee break |
| Chair: | Martin Dyer |
| 11:00 - 11:30 | Gregory Sorkin (IBM) Optimal Myoptic Algorithms for Random 3SAT |
| 11:30 - 12:00 | Graham Brightwell (London) Connectivity among H-colorings |
| 12:15 | Lunch break |
| Chair: | Mark Jerrum |
| 15:00 - 15:30 | Claire Kenyon (Paris-Sud) Coalescing Particles on a Tree |
| 15:30 - 16:00 | Michael Langberg (Weizmann Institute) The RPR2 Rounding Technique for Semidefinite Programs |
| 16:00 - 16:30 | Coffee break |
| Chair: | Alan Frieze |
| 16:30 - 17:00 | Malwina Luczak (Oxford) Routing Random Calls on Graphs |
| 17:00 - 17:30 | Dana Randall (Georgia Tech) Decomposition Swapping + Mean Field Models |
| 18:00 | Dinner |
Tuesday, June 5th, 2001
| Chair: | Ravi Kannan |
| 09:00 - 09:30 | Marek Karpinski (Bonn) Approximability of Dense Nearest Codeword Problem |
| 09:30 - 10:00 | Mark Jerrum (Edinburgh) A Polynomial-Time Approximation Algorithms for the Permanent of a Matrix with Non-Negative Entries, Part I |
| 10:00 - 10:30 | Eric Vigoda (Edinburgh) A Polynomial-Time Approximation Algorithms for the Permanent of a Matrix with Non-Negative Entries, Part II |
| 10:30 - 11:00 | Coffee break |
| Chair: | Sanjeev Khanna |
| 11:00 - 11:30 | Piotr Berman (Bonn) Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION |
| 11:30 - 12:00 | Alex D. Scott (London) Judicious Partitions of Graphs and Hypergraphs |
| 12:15 | Lunch break |
| Chair: | Sanjeev Arora |
| 15:00 - 15:30 | W. Fernandez de la Vega (Paris-Sud) Sampling k-Uniform Hypergraphs and Design of PTASs for Dense Instances of Min-CSP |
| 15:30 - 16:00 | Jennifer Chayes (Microsoft) The Phase Transition in the Random Partition Problem |
| 16:00 - 16:30 | Coffee break |
| Chair: | Alexander Barvinok |
| 16:30 - 17:00 | Angelika Steger (München) A New Performance Measure for Stochastic Scheduling |
| 17:00 - 17:30 | Christian Borgs (Microsoft) Slow Mixing for H-Colorings of the Hypercubic Lattice |
| 18:00 | Dinner |
Wednesday, June 6th, 2001
| Chair: | Jennifer Chayes |
| 09:00 - 09:30 | Eli Upfal (Brown) Can Entropy Predict On-Line Performance? |
| 09:30 - 10:00 | M. Karonski (Poznan) Distributed Graph Coloring Algorithms |
| 10:00 - 10:30 | Miklos Santha (Paris-Sud) Quantum Algorithms for Some Instances of the Hidden Subgroup Problem |
| 10:30 - 11:00 | Coffee break |
| Chair: | W. Fernandez de la Vega |
| 11:00 - 11:30 | Klaus Jansen (Kiel) Polynomial-time Approximation Schemes for Preemptive Resource Constrained Scheduling and Fractional Graph Coloring |
| 11:30 - 12:00 | Catherine Greenhill (Melbourne) Connectedness of Bounded Degree Star Processes |
| 12:15 | Lunch break |
| 13:30 - 17:30 | Excursion |
| 18:00 | Dinner |
| 20:00 | Evening Session |
| Chair: | Alexander Barvinok |
Thursday, June 7th, 2001
| Chair: | Claire Kenyon |
| 09:00 - 09:30 | Sanjeev Arora (Princeton) On On-Line Algorithms for Bandwidth Utilization |
| 09:30 - 10:00 | Alexander Barvinok (Michigan) Metric Geometry of Counting |
| 10:00 - 11:00 | Coffee break |
| Chair: | Michael Paterson |
| 11:00 - 11:45 | Ravi Kannan (Yale) What Can You Do in One or Two Passes |
| 11:45 - 12:15 | Colin Cooper (London) Random Graphs Which Model the Internet |
| 12:15 | Lunch break |
| Chair: | Eli Upfal |
| 15:00 - 15:30 | David B. Wilson (Microsoft) Perfect Simulation for Quenchal Disordered Systems |
| 15:30 - 16:00 | Petra Berenbrink (Warwick) The Natural Work Stealing Algorithm is Stable |
| 16:00 - 16:30 | Coffee break |
| Chair: | Gerhard Woeginger |
| 16:30 - 17:00 | Artur Czumaj (NJIT) On Certain Property Testing Algorithms |
| 17:00 - 17:30 | Thomas Jansen (Dortmund) On the Analysis of Evolutionary Algorithms |
| 18:00 | Dinner |
Friday, June 8th, 2001
| Chair: | Graham R.Brightwell |
| 09:00 - 09:30 | Jung-Bae Son (Edinburgh) Average Conductance and Log-Sobolev Constant of Balanced Matroids |
| 09:30 - 10:00 | Piotr Krysta (MPI Saarbrücken) Approximating Minimum Size 2-Connectivity Problems Using Local Search |
| 10:00 - 10:30 | Lars Engebretsen (MIT) Approximation Hardness of Traveling Salesman Problem with Bounded Metric |
End of Workshop
| 10:30 - 11:00 | Coffee |
| 12:15 | Lunch |