September 1 - December 18, 2015
Organizers: András Frank, Satoru Iwata, Jochen Könemann, Jens Vygen
Description: Combinatorial optimization is an active field leveraging ideas from many different areas including graph theory, combinatorics, matroid theory, submodularity, connectivity, network flows, approximation algorithms, mathematical programming, game theory, algebraic and geometric methods, and applications. This trimester program was intended to bring together the field's best researchers focusing on the discovery of new connections, and to establish new and deepen existing international collaborations.
Associated Events: We hosted long-term visitors and organized four workshops during the program, on the broad topics
- Connectivity, Routing, and Network Design (Sep 7-11);
- Rigidity, Submodularity, and Discrete Convexity (Oct 5-9);
- Relaxations and Polyhedral Methods (Nov 16-20);
- Algorithmic and Computational Game Theory (Dec 14-17).
- A summer school on combinatorial optimization took place from September 21 to 25.
© HIM
No. |
Author(s) |
Title |
Preprint |
Publication |
| 2015c01 | Gottschalk, Corinna; Vygen, Jens | Better s-t-tours by Gao trees | 1511.05514 | MR3534727 |
| 2015c02 | Newman, Alantha; Röglin, Heiko; Seif, Johanna | The alternating stock size problem and the gasoline puzzle | 1511.09259 | MR3550134 |
| 2015c03 | Singh, Mohit; Zenklusen, Rico | k-trails: recognition, complexity, and approximations | 1512.01781 | MR3534726 |
| 2015c04 | Fujishige, Satoru; Tanigawa, Shin-ichi | Polynomial combinatorial algorithms for skew-bisubmodular function minimization | MR3844535 | |
| 2015c05 | Borgwardt, Steffen; De Loera, Jesús A.; Finhold, Elisabeth | The diameters of transportation polytopes satisfy the Hirsch conjecture | 1603.00325 | |
| 2015c06 | Feldmann, Andreas Emil; Fung, Wai Shing; Könemann, Jochen; Post, Ian | A (1+ε)-embedding of low highway dimension graphs into bounded treewidth graphs | 1502.04588 | MR3382460 |
| 2015c07 | Feldmann, Andreas Emil; Könemann, Jochen; Pashkovich, Kanstantsin; Sanità, Laura | Fast approximation algorithms for the generalized survivable network design problem | 1604.07049 | MR3598412 |
| 2015c08 | Friggstad, Zachary; Könemann, Jochen; Shadravan, Mohammad | A logarithmic integrality gap bound for directed Steiner tree in quasi-bipartite graphs | 1604.08132 | MR3539190 |
| 2015c09 | Könemann, Jochen; Pashkovich, Kanstantsin; Toth, Justin | An elementary integrality proof of Rothblum's stable matching formulation | 1605.04427 | MR3573195 |
| 2015c10 | Sebő, András; van Zuylen, Anke | The salesman's improved paths: a 3/2+1/34 approximation | 1604.02486 | MR3630972 |
| 2015c11 | Conforti, Michele; Wolsey, Laurence A. | "Facet" separation with one linear program | MR4019954 | |
| 2015c12 | Mnich, Matthias; Williams, Virginia Vassilevska; Végh, László A. | A 7/3-approximation for feedback vertex sets in tournaments | 1511.01137 | MR3550130 |
| 2015c13 | Abdi, Ahmad; Cornuéjols, Gérard; Pashkovich, Kanstantsin | Ideal clutters that do not pack | ||
| 2015c14 | Ahmadian, Sara; Swamy, Chaitanya | Approximation algorithms for clustering problems with lower bounds and outliers | 1608.01700 | MR3577130 |
| 2015c15 | Fiorini, Samuel; Huynh, Tony; Joret, Gwenaël; Pashkovich, Kanstantsin | Smaller extended formulations for the spanning tree polytope of bounded-genus graphs | 1604.07976 | MR3614780 |
| 2015c16 | Pashkovich, Kanstantsin | Every rational polyhedron has finite split rank: new proof | 1606.05811 | |
| 2015c17 | Olver, Neil; Végh, László A. | A simpler and faster strongly polynomial algorithm for generalized flow maximization | 1611.01778 | MR3678174 |
| 2015c18 | Fortier, Quentin; Király, Csaba; Szigeti, Zoltán; Tanigawa, Shin-ichi | On packing spanning arborescences with matroid constraint | link, pdf | MR4043756 |
| 2015c19 | Bazzi, Abbas; Fiorini, Samuel; Huang, Sangxia; Svensson, Ola | Small extended formulation for knapsack cover inequalities from monotone circuits | 1609.03737 | MR3885413 |
| 2015c20 | Dadush, Daniel; Regev, Oded | Towards strong reverse Minkowski-type inequalities for lattices | 1606.06913 | MR3631007 |
| 2015c21 | Dadush, Daniel; Végh, László A.; Zambelli, Giacomo | Rescaling algorithms for linear programming - part I: conic feasibility | 1611.06427 | |
| 2015c22 | van Zuylen, Anke | Improved approximations for cubic and cubic bipartite TSP | 1507.07121 | MR3865720 |
| 2015c23 | Jackson, Bill; Nixon, Anthony | Global rigidity of generic frameworks on concentric cylinders | 1610.07755 | |
| 2015c24 | Panageas, Ioannis; Piliouras, Georgios | Gradient descent only converges to minimizers: non-isolated critical points and invariant regions | 1605.00405 | MR3754926 |
| 2015c25 | Mehta, Ruta; Panageas, Ioannis; Piliouras, Georgios; Tetali, Prasad; Vazirani, Vijay V. | Mutation, sexual reproduction and survival in dynamic environments | 1511.01409 | MR3754940 |
| 2015c26 | Chandrasekaran, Karthekeyan; Gottschalk, Corinna; Könemann, Jochen; Peis, Britta; Schmand, Daniel; Wierz, Andreas | Additive stabilizers for unstable graphs | 1608.06797 | MR3927009 |
| 2015c27 | Annamalai, Chidambaram | Finding perfect matchings in bipartite hypergraphs | 1509.07007 | MR3478502 |
| 2015c28 | Chakrabarty, Deeparnab; Lee, Yin Tat; Sidford, Aaron; Wong, Sam Chiu-wai | Subquadratic submodular function minimization | 1610.09800 | MR3678265 |
| 2015c29 | Lee, Jon; Skipper, Daphne | Virtuous smoothing for global optimization | 1605.05221 | MR3714557 |
| 2015c30 | Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fabio | Scaling, proximity, and optimization of integrally convex functions | 1703.10705 | MR39428885 |
| 2015c31 | Connelly, Robert; Gortler, Steven J.; Theran, Louis | Generic global and universal rigidity | 1604.07475 | |
| 2015c32 | Chekuri, Chandra; Xu, Chao | Computing minimum cuts in hypergraphs | 1607.08682 | MR3627799 |
| 2015c33 | Chekuri, Chandra | Some open problems in element-connectivity | ||
| 2015c34 | Kaszanitzky, Viktoria E.; Schulze, Bernd; Tanigawa, Shin-ichi | Global rigidity of periodic graphs under fixed-lattice representations | 1612.01379 | MR4155281 |
| 2015c35 | Arulselvan, Ashwin; Cseh, Ágnes; Groß, Martin; Manlove, David F.; Matuschke, Jannik | Matchings with lower quotas: algorithms and complexity | 1412.0325 | MR3741541 |
| 2015c36 | Iwamasa, Yuni; Murota, Kazuo; Zivny, Stanislav | Discrete convexity in joint winner property | 1701.07645 | MR3799038 |
| 2015c37 | Palaiopanos, Gerasimos; Panageas, Ioannis; Piliouras, Georgios | Multiplicative weights update with constant step-size in congestion games: convergence, limit cycles and chaos | 1703.01138 | |
| 2015c38 | Eftekhari, Yaser; Jackson, Bill; Nixon, Anthony; Schulze, Bernd; Tanigawa, Shin-ichi; Whiteley, Walter | Point-hyperplane frameworks, slider joints, and rigidity preserving transformations | 1703.06844 | MR3926261 |
| 2015c39 | Abdi, Ahmad; Pashkovich, Kanstantsin | Deltas, delta minors and delta free clutters | MR3831239 | |
| 2015c40 | Bérczi, Kristóf; Frank, András | Supermodularity in unweighted graph optimization I: branchings and matchings | 1608.05722 | MR3846069 |
| 2015c41 | Bérczi, Kristóf; Frank, András | Supermodularity in unweighted graph optimization II: matroidal term rank augmentation | 1608.05730 | MR3846070 |
| 2015c42 | Bérczi, Kristóf; Frank, András | Supermodularity in unweighted graph opitimization III: highly-connected digraphs | 1608.05729 | to appear in Mathematics of Operations Research |
| 2015c43 | Könemann, Jochen; Olver, Neil; Pashkovich, Kanstantsin; Ravi, Ramamoorthi; Swamy, Chaitanya; Vygen, Jens | On the integrality gap of the prize-collecting Steiner forest LP | 1706.06565 | MR3695584 |
| 2015c44 | Dadush, Daniel; Végh, László A.; Zambelli, Giacomo | Rescaled coordinate descent methods for linear programming | MR3534719 | |
| 2015c45 | Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fabio | Discrete midpoint convexity | 1708.04579 | MR4066991 |
| 2015c46 | Calinescu, Gruia; Kortsarz, Guy; Nutov, Zeev | Improved approximation algorithms for Minimum Power Covering problems | Preprint | MR4018001 |
Name |
Affiliation |
| Ahmad Abdi | University of Waterloo |
| Hyung-Chan An | EPFL |
| Joergen Bang-Jensen | University of Southern Denmark |
| Nikhil Bansal | TU Eindhoven |
| Gruia Calinescu | Illinois Institute of Technology |
| 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 |
| Jesus De Loera | University of California |
| Marco Di Summa | Università degli Studi di Padova |
| Friedrich Eisenbrand | EPFL |
| Yuri Faenza | EPFL |
| Linda Farczadi | EPFL |
| Andreas Feldmann | MTA SZTAKI |
| Andreas Feldmann | MTA SZTAKI |
| Elisabeth Finhold | UC Davis |
| Samuel Fiorini | Université libre de Bruxelles |
| Anja Fischer | Georg-August-Universität Göttingen |
| András Frank | Eotvos University Budapest |
| Satoru Fujishige | Research Institute for Mathematical Sciences |
| Shashwat Garg | TU Eindhoven |
| Michel Goemans | MIT |
| Corinna Gottschalk | RWTH Aachen |
| Anupam Gupta | Carnegie Mellon University |
| Stephan Held | Universität Bonn |
| Stefan Hougardy | Universität Bonn |
| Nicolai Hähnle | Universität Bonn |
| Satoru Iwata | University of Tokyo |
| Zsuzsanna Jankó | Eötvös Loránd University |
| Tibor Jordán | Eötvös University |
| Volker Kaibel | Otto-von-Guericke Universität Magdeburg |
| Marek Karpinski | Universität Bonn |
| Bernhard Korte | Universität Bonn |
| Jochen Könemann | University of Waterloo |
| Monique Laurent | CWI |
| Yin Tat Lee | Massachusetts Institute of Technology |
| Jonathan Lee | University of Michigan |
| Jannik Matuschke | TU Berlin |
| S Thomas McCormick | Sauder School of Business, UBC |
| Ruta Mehta | Georgia Institute of Technology |
| Matthias Mnich | Universität Bonn |
| Kazuo Murota | Tokyo Metropolitan University |
| Alantha Newman | CNRS |
| Tony Nixon | Lancaster University |
| Zeev Nutov | The Open University of Israel |
| Neil Olver | VU University Amsterdam & CWI |
| Gyula Pap | Eötvös University |
| Kanstantsin Pashkovich | University of Waterloo |
| Britta Peis | RWTH Aachen |
| Georgios Piliouras | Singapore University of Technology and Design |
| Matthias Poloczek | Cornell University |
| Kirk Pruhs | University of Pittsburgh |
| Ramamoorthi Ravi | Carnegie Mellon University |
| Bruce Reed | McGill University |
| Thomas Rothvoss | University of Washington |
| Heiko Röglin | Universität Bonn |
| Kevin Schewior | TU Berlin |
| András Sebo | CNRS |
| Bruce Shepherd | McGill University |
| David Shmoys | Cornell University |
| Bernhard von Stengel | London School of Economics |
| Leen Stougie | VU University Amsterdam |
| Ola Svensson | EPFL |
| Chaitanya Swamy | University of Waterloo |
| Zoltán Szigeti | Grenoble Institute of Technology |
| Shin-ichi Tanigawa | Kyoto University |
| Louis Theran | Aalto University |
| Jan Vondrák | IBM Almaden Research Center |
| 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 |
This list does not include people who only participated in workshops.
© HIM