November 16-20, 2015
HIM Lecture Hall, Poppelsdorfer Allee 45
Organizers:
Nikhil Bansal, Ola Svensson, Jens Vygen, David Williamson
Topics: Relaxations and Polyhedral Methods
Main speakers:
- Michel Goemans
- Monique Laurent
- James Lee
- Aravind Srinivasan
© HIM
Monday, November 16
| 10:15 - 10:50 | Registration & Welcome coffee |
| 10:50 - 11:00 | Opening remarks |
| 11:00 - 11:30 | Mohit Singh: Maximizing Determinants under Partition Constraints |
| 11:30 - 12:00 | Rico Zenklusen: Online Contention Resolution Schemes |
| 12:00 - 15:00 | Lunch break and discussions |
| 15:00 - 15:30 | Ramamoorthi Ravi: Designing Overlapping Networks for Publish-Subscribe Systems |
| 15:30 - 16:00 | Christos Kalaitzis: Approximating the Maximum Budgeted Allocation Problem using the Configuration-LP |
| 16:00 - 16:30 | Tea and cake |
| 16:30 - 17:00 | Daniel Dadush: On the Geometry of Linear Programming |
| 17:00 - 17:30 | Parinya Chalermsook: Graph products, hardness of approximation, and beyond |
| 20:00 - | Concert at the Arithmeum (Lennéstrasse 2): Gruppo Ocarinistico Budriese |
Tuesday, November 17
| 9:30 - 10:30 | James Lee: Lower bounds on the size of SDP relaxations |
| 10:30 - 11:00 | Coffee break and group photo |
| 11:00 - 11:30 | Volker Kaibel: A simple geometric proof showing that almost all 0/1-polytopes have exponential semidefinite extension complexity |
| 11:30 - 12:00 | Samuel Fiorini: No Small Linear Program Approximates Vertex Cover within a Factor 2-ε |
| 12:00 - 14:00 | Lunch break |
| 14:00 - 16:00 | Discussion session |
| 16:00 - 16:30 | Tea and cake |
| 16:30 - 17:00 | Stanislav Zivny: The power of Sherali-Adams relaxations for general-valued CSPs |
| 17:00 - 17:30 | Sebastian Pokutta: Affine reductions in Extended Formulations |
| afterwards | Reception |
Wednesday, November 18
| 9:30 - 10:30 | Monique Laurent: Convergence analysis of hierarchies for polynomial optimization |
| 10:30 - 11:00 | Coffee break |
| 11:00 - 11:30 | Jon Lee: Comparing polyhedral relaxations via volume |
| 11:30 - 12:00 | Monaldo Mastrolilli: On some easy problems that are hard for the Lasserre hierarchy |
| 12:00 - 15:00 | Lunch break and discussions |
| 15:00 - 15:30 | Anja Fischer: Polynomial Matroid Optimisation Problems |
| 15:30 - 16:00 | Alantha Newman: The Alternating Stock Size Problem and the Gasoline Puzzle |
| 16:00 - 16:30 | Tea and cake |
| 16:30 - 17:00 | Robert Weismantel: Affine TU decomposition of matrices |
| 17:00 - 17:30 | Jonas Witt: Dantzig-Wolfe Reformulations for the Stable Set Problem |
Thursday, November 19
| 9:30 - 10:30 | Michel Goemans: Rounding linear programs: A few recent examples |
| 10:30 - 11:00 | Coffee break |
| 11:00 - 11:30 | Sylvia Boyd: Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem |
| 11:30 - 12:00 | David Shmoys: Approximation algorithms for a bike-sharing rebalancing problem |
| 12:00 - 14:00 | Lunch break |
| 14:00 - 16:00 | Discussion session |
| 16:00 - 16:30 | Tea and cake |
| 16:30 - 17:00 | Chidambaram Annamalai: Finding Perfect Matchings in Bipartite Hypergraphs |
| 17:00 - 17:30 | Matthias Mnich: Improved Approximation Algorithm for Minimum Feedback Vertex Sets in Tournaments |
| 18:00 - 19:00 | Arithmeum tour (We walk together from HIM, leaving at 17:45.) |
Friday, November 20
| 9:30 - 10:00 | Nisheeth Vishnoi: Natural Algorithms for Flow Problems |
| 10:00 - 10:30 | Viswanath Nagarajan: Approximation-Friendly Discrepancy Rounding |
| 10:30 - 11:00 | Coffee break |
| 11:00 - 12:00 | Aravind Srinivasan: Approximating integer-programming problems by partial resampling |
| 12:00 - 14:00 | Lunch break |
| 14:00 - 16:00 | Discussion session |
| 16:00 - 16:30 | Tea and cake – end of workshop |
Person |
Affiliation |
Period of stay |
| Ahmad Abdi | University of Waterloo | |
| Sara Ahmadian | University of Waterloo | |
| Hyung-Chan An | EPFL | |
| Chidambaram Annamalai | ETHZ | |
| Nikhil Bansal | TU Eindhoven | |
| Sylvia Boyd | University of Ottawa | |
| Parinya Chalermsook | Max Planck Institute for Informatics | |
| Karthekeyan Chandrasekaran | University of Illinois, Urbana-Champaign | |
| Joseph Cheriyan | University of Waterloo | |
| Michelangelo Conforti | Università di Padova | |
| William Cook | University of Waterloo | |
| Gerard Cornuejols | Carnegie Mellon University | |
| Agnes Cseh | TU Berlin | |
| Daniel Dadush | Centrum Wiskunde en Informatica | |
| Marco Di Summa | Università degli Studi di Padova | |
| Yuri Faenza | EPFL | |
| Elisabeth Finhold | UC Davis | |
| Samuel Fiorini | Université libre de Bruxelles | |
| Anja Fischer | Georg-August-Universität Göttingen | |
| Michel Goemans | MIT | |
| Corinna Gottschalk | RWTH Aachen | |
| Fabrizio Grandoni | IDSIA, University of Lugano | |
| Stephan Held | Universität Bonn | |
| Stefan Hougardy | Universität Bonn | |
| Volker Kaibel | Otto-von-Guericke Universität Magdeburg | |
| Christos Kalaitzis | EPFL | |
| Marek Karpinski | Universität Bonn | |
| Bernhard Korte | Universität Bonn | |
| Jochen Könemann | University of Waterloo | |
| Monique Laurent | CWI | |
| James Lee | University of Washington | |
| Jonathan Lee | University of Michigan | |
| Monaldo Mastrolilli | IDSIA | |
| Jannik Matuschke | TU Berlin | |
| Matthias Mnich | Universität Bonn | |
| Viswanath Nagarajan | University of Michigan | |
| Seffi Naor | Technion | |
| Alantha Newman | CNRS | |
| Neil Olver | VU University Amsterdam & CWI | |
| Kanstantsin Pashkovich | University of Waterloo | |
| Britta Peis | RWTH Aachen | |
| Sebastian Pokutta | Georgia Institute of Technology | |
| Ramamoorthi Ravi | Carnegie Mellon University | |
| Heiko Röglin | Universität Bonn | |
| András Sebo | CNRS | |
| David Shmoys | Cornell University | |
| Mohit Singh | Microsoft Corporation | |
| Aravind Srinivasan | University of Maryland | |
| Ola Svensson | EPFL | |
| Chaitanya Swamy | University of Waterloo | |
| Shin-ichi Tanigawa | Kyoto University | |
| Louis Theran | Aalto University | |
| Nisheeth Vishnoi | EPFL | |
| Jens Vygen | Universität Bonn | |
| Robert Weismantel | ETH Zurich | |
| David Williamson | Cornell University | |
| Jonas Witt | RWTH Aachen University | |
| Laurence Wolsey | CORE, Universite catholique de Louvain | |
| Rico Zenklusen | ETH Zurich | |
| Stanislav Zivny | University of Oxford | |
| Anke van Zuylen | College of William & Mary |