Centre de recherches mathématiques
|
||
|
LUNDI 12 juin / MONDAY, June 12
|
||
| 08:30 - 09:00 | Inscription / Registration (1er étage / 1st floor, Pavillon Andre-Aisenstadt) Café / Coffee (Salle / Room 6245) | |
| 09:00 - 09:45 | Lap Chi Lau (University of Toronto) On Steiner rooted-orientations of graphs and hypergraphs |
|
| 09:45 - 10:30 | Lisa Fleischer (IBM T. J. Watson Research Center) Cost shares and approximation algorithms for network design problems |
|
| 10:30 - 11:00 | Pause café / Coffee Break (Salle / Room 6245) | |
| 11:00 - 11:30 | Yuval Rabani (Technion) Approximation algorithms for graph homomorphism problems |
|
| 11:30 - 12:00 | Anupam Gupta (Carnegie Mellon University) Oblivious network design |
|
| 12:00 - 14:00 | Lunch (Salle / Room 6245) | |
| 14:00 - 14:30 | Uriel Feige (Microsoft Research) On maximizing welfare when utility functions are subadditive |
|
| 14:30 - 15:00 | Jan Vondrak (Microsoft Research) Approximation algorithms for allocation problems: improving 1-1/e |
|
| 15:00 - 15:30 | Andreas Schulz (MIT) The least core value of schedule planning games |
|
| 15:30 - 16:00 | Pause café / Coffee Break (Salle / Room 6245) | |
| 16:00 - 16:45 | David Shmoys (Cornell University) Approximation algorithms for stochastic inventory control models |
|
| 16:45 - 17:30 | Chandra Chekuri (Lucent Bell Labs) Maximizing submodular set functions revisited |
|
| 18:00 | Réception de bienvenue / Welcoming Reception | |
|
MARDI 13 juin / TUESDAY, June 13
|
||
| 08:30 - 09:00 | Café / Coffee (Salle / Room 6245) |
|
| 09:00 - 09:45 | Bruce Shepherd (Lucent Bell Labs) Disjoint paths in planar graphs |
|
| 09:45 - 10:30 | Matthew Andrews (Lucent Bell Labs) Hardness of routing problems in high-girth graphs |
|
| 10:30 - 11:00 | Pause café / Coffee Break (Salle / Room 6245) | |
| 11:00 - 11:30 | Mohammad Salavatipour (University of Alberta) Approximation and hardness results for packing cycles |
|
| 11:30 - 12:00 | Guy Kortsarz (Rutgers University-Camden) Approximation algorithms for non-uniform buy-at-bulk network design problems |
|
| Lunch | ||
| 14:00 - 14:45 | Subhash Khot (Georgia Institute of Technology) Hardness of approximating the shortest vector problem in lattices |
|
| 14:45 - 15:30 | Moses Charikar (Princeton University) Near-optimal algorithms for unique games |
|
| 15:30 - 16:00 | Pause café / Coffee Break (Salle / Room 6245) | |
| 16:00 - 16:45 | Sanjeev Arora (Princeton University) Multiplicative Weight Method: A general algorithmic tool (with applications to linear and semidefinite programming) |
|
| 16:45 - 17:30 | Naveen Garg (Indian Institute of Technology) Minimizing average flow-time on related machines |
|
|
MERCREDI 14 juin / WEDNESDAY, June 14
|
||
| 08:30 - 09:00 | Café / Coffee (Salle / Room 6245) |
|
| 09:00 - 09:30 | David Williamson (Cornell University) A general approach for incremental approximation and hierarchical clustering |
|
| 09:30 - 10:00 | Robi Krauthgamer (IBM Almaden Research Center) Algorithms on negatively curved spaces |
|
| 10:00 - 10:30 | Kamal Jain (Microsoft Research) Dimension of a poset and constraint feedback arc set problem |
|
| 10:30 - 11:00 | Pause café / Coffee Break (Salle / Room 6245) | |
| 11:00 - 11:30 | Jochen Konemann (University of Waterloo) A fresh look at Steiner trees: greedy vs primal-dual algorithms |
|
| 11:30 - 12:00 | Vahab Mirrokni (MIT) Approximation Algorithms for Power Optimization in Wireless Networks |
|
| Lunch | ||
| 14:00 - 14:30 | Adrian Vetta (McGill University) Graph connectivity and malicious attacks |
|
| 14:30 - 15:00 | Sylvia Boyd (University of Ottawa) On the integrality gap for the minimum cost 2-edge connected multi-subgraph problem |
|
| 15:00 - 15:30 | R. Ravi (Carnegie Mellon University) Delegate and conquer: An LP-based approximation algorithm for minimum degree MSTs |
|
| 15:30 - 16:15 | Michel Goemans (MIT) Bounded-degree minimum spanning trees |
|
| 16:15 | Café de départ / Farewell Coffee (Salle / Room 6245) | |