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, C.; Vygen, J. | Better s-t-tours by Gao trees | 1511.05514 | Lecture Notes in Comput. Sci., 9682 https://doi.org/10.1007/978-3-319-33461-5_11 |
| 2015c02 | Newman, A.; Röglin, H.; Seif, J. | The alternating stock size problem and the gasoline puzzle | 1511.09259 | ACM Transactions on Algorithms. 14(2) 19 (20018), 1 - 23. https://doi.org/10.1145/3178539 |
| 2015c03 | Singh, M.; Zenklusen, R. | k-trails: recognition, complexity, and approximations | 1512.01781 | Math. Program. 172 (2018), 169–189. https://doi.org/10.1007/s10107-017-1113-z |
| 2015c04 | Fujishige, S.; Tanigawa, S.-i. | Polynomial combinatorial algorithms for skew-bisubmodular function minimization | Math. Program. 171(1-2) (2018), 87–114. https://doi.org/10.1007/s10107-017-1171-2 |
|
| 2015c05 | Borgwardt, S.; De Loera, J. A.; Finhold, E. | The diameters of transportation polytopes satisfy the Hirsch conjecture | 1603.00325 | |
| 2015c06 | Feldmann, A. E.; Fung, W. S.; Könemann, J.; Post, I. | A (1+ε)-embedding of low highway dimension graphs into bounded treewidth graphs | 1502.04588 | SIAM Journal on Computing. 47(4) (2018), 1667 – 1704. https://doi.org/10.1137/16M1067196 |
| 2015c07 | Feldmann, A. E.; Könemann, J.; Pashkovich, K.; Sanità, L. | Fast approximation algorithms for the generalized survivable network design problem | 1604.07049 | ISAAC 2016. 64(33) (2016), 12. https://doi.org/10.4230/LIPIcs.ISAAC.2016.33 |
| 2015c08 | Friggstad, Z.; Könemann, J.; Shadravan, M. | A logarithmic integrality gap bound for directed Steiner tree in quasi-bipartite graphs | 1604.08132 | SWAT 2016. 53 (2016), 3:1-3:11. https://doi.org/10.4230/LIPIcs.SWAT.2016.3 |
| 2015c09 | Könemann, J.; Pashkovich, K.; Toth, J. | An elementary integrality proof of Rothblum's stable matching formulation | 1605.04427 | Oper. Res. Lett.44(2016), no.6, 754–756. https://doi.org/10.1016/j.orl.2016.09.011 |
| 2015c10 | Sebő, A.; van Zuylen, A. | The salesman's improved paths: a 3/2+1/34 approximation | 1604.02486 | EEE 57th FOCS. (2016), 118-127. https://doi.ieeecomputersociety.org/10.1109/FOCS.2016.21 |
| 2015c11 | Conforti, M.; Wolsey, L. A. | "Facet" separation with one linear program | Math. Program. 178(1-2) (2019), 361–380. https://doi.org/10.1007/s10107-018-1299-8 |
|
| 2015c12 | Mnich, M.; Williams, V. V.; Végh, L. A. | A 7/3-approximation for feedback vertex sets in tournaments | 1511.01137 | ESA 2016. 57 (2016), 67:1-67:14. https://doi.org/10.4230/LIPIcs.ESA.2016.67 |
| 2015c13 | Abdi, A.; Cornuéjols, G.; Pashkovich, K. | Ideal clutters that do not pack | Pack. Mathematics of Operations Research. 43(2) (2017), 533-553. https://doi.org/10.1287/moor.2017.0871 |
|
| 2015c14 | Ahmadian, S.; Swamy, C. | Approximation algorithms for clustering problems with lower bounds and outliers | 1608.01700 | ICALP 2016. 55 (2016), 69:1-69:15. https://doi.org/10.4230/LIPIcs.ICALP.2016.69 |
| 2015c15 | Fiorini, S.; Huynh, T.; Joret, G.; Pashkovich, K. | Smaller extended formulations for the spanning tree polytope of bounded-genus graphs | 1604.07976 | Discrete Comput. Geom. 57(3) (2017), 757–761. https://doi.org/10.1007/s00454-016-9852-9 |
| 2015c16 | Pashkovich, K. | Every rational polyhedron has finite split rank: new proof | 1606.05811 | |
| 2015c17 | Olver, N.; Végh, L. A. | A simpler and faster strongly polynomial algorithm for generalized flow maximization | 1611.01778 | Journal of the ACM (JACM). 67(2) 10 (2020), 1 – 26. https://doi.org/10.1145/3383454 |
| 2015c18 | Fortier, Q.; Király, C.; Szigeti, Z.; Tanigawa, S-i. | On packing spanning arborescences with matroid constraint | link, pdf | J. Graph Theory. 93(2) (2020), 230–252. https://doi.org/10.1002/jgt.22484 |
| 2015c19 | Bazzi, A.; Fiorini, S.; Huang, S.; Svensson, O. | Small extended formulation for knapsack cover inequalities from monotone circuits | 1609.03737 | Theory Comput. 14(14) (2018), 29. https://doi.org/10.4086/toc.2018.v014a014 |
| 2015c20 | Dadush, D.; Regev, O. | Towards strong reverse Minkowski-type inequalities for lattices | 1606.06913 | FOCS 2016. (2016), 447-456. https://doi.org/10.1109/FOCS.2016.55 |
| 2015c21 | Dadush, D.; Végh, L. A.; Zambelli, G. | Rescaling algorithms for linear programming - part I: conic feasibility | 1611.06427 | |
| 2015c22 | van Zuylen, A. | Improved approximations for cubic and cubic bipartite TSP | 1507.07121 | Math. Program. 172(1-2) (2018), 399–413. https://doi.org/10.1007/s10107-017-1211-y |
| 2015c23 | Jackson, B.; Nixon, A. | Global rigidity of generic frameworks on concentric cylinders | 1610.07755 | J. Combin. Theory Ser. 139 (2019), 193–229. https://doi.org/10.1016/j.jctb.2019.03.002 |
| 2015c24 | Panageas, I.; Piliouras, G. | Gradient descent only converges to minimizers: non-isolated critical points and invariant regions | 1605.00405 | ITCS 2017. 67 (2017), 2:1-2:12. https://doi.org/10.4230/LIPIcs.ITCS.2017.2 |
| 2015c25 | Mehta, R.; Panageas, I.; Piliouras, G.; Tetali, P.; Vazirani, V. V. | Mutation, sexual reproduction and survival in dynamic environments | 1511.01409 | ITCS 2017. 67 (2017), 16:1-16:29. https://doi.org/10.4230/LIPIcs.ITCS.2017.16 |
| 2015c26 | Chandrasekaran, K.; Gottschalk, C.; Könemann, J.; Peis, B.; Schmand, D.; Wierz, A. | Additive stabilizers for unstable graphs | 1608.06797 | Discrete Optim.31 (2019), 56–78. https://doi.org/10.1016/j.disopt.2018.08.003 |
| 2015c27 | Annamalai, C. | Finding perfect matchings in bipartite hypergraphs | 1509.07007 | Combinatorica. 38 (2018), 1285–1307. https://doi.org/10.1007/s00493-017-3567-2 |
| 2015c28 | Chakrabarty, D.; Lee, Y. T.; Sidford, A.; Wong, Sam C-w. | Subquadratic submodular function minimization | 1610.09800 | STOC 2017. (2017, 1220 – 1231. https://doi.org/10.1145/3055399.3055419 |
| 2015c29 | Lee, J.; Skipper, D. | Virtuous smoothing for global optimization | 1605.05221 | J. Global Optim. 69(3) (2017), 677–697. https://doi.org/10.1007/s10898-017-0533-x |
| 2015c30 | Moriguchi, S.; Murota, K.; Tamura, A.; Tardella, F. | Scaling, proximity, and optimization of integrally convex functions | 1703.10705 | Math. Program.175(1-2) (2019), 119–154. https://doi.org/10.1007/s10107-018-1234-z |
| 2015c31 | Connelly, R.; Gortler, S. J.; Theran, L. | Generic global and universal rigidity | 1604.07475 | |
| 2015c32 | Chekuri, C.; Xu, C. | Computing minimum cuts in hypergraphs | 1607.08682 | Symposium on Discrete Algorithms. (2017), 1085 – 1100. https://doi.org/10.1137/1.9781611974782.70 |
| 2015c33 | Chekuri, C. | Some open problems in element-connectivity | ||
| 2015c34 | Kaszanitzky, V. E.; Schulze, B.; Tanigawa, S-i. | Global rigidity of periodic graphs under fixed-lattice representations | 1612.01379 | J. Combin. Theory Ser. 146 (2021), 176–218. https://doi.org/10.1016/j.jctb.2020.09.009 |
| 2015c35 | Arulselvan, A.; Cseh, Á.; Groß, M.; Manlove, D. F.; Matuschke, J. | Matchings with lower quotas: algorithms and complexity | 1412.0325 | Algorithmica. 80(1) (2018), 185–208. https://doi.org/10.1007/s00453-016-0252-6 |
| 2015c36 | Iwamasa, Y.; Murota, K.; Zivny, S. | Discrete convexity in joint winner property | 1701.07645 | Discrete Optim. 28 (2018), 78–88. https://doi.org/10.1016/j.disopt.2018.01.001 |
| 2015c37 | Palaiopanos, G.; Panageas, I.; Piliouras, G. | Multiplicative weights update with constant step-size in congestion games: convergence, limit cycles and chaos | 1703.01138 | NIPS'17. (2017), 5874 – 5884. https://dl.acm.org/doi/10.5555/3295222.3295337 |
| 2015c38 | Eftekhari, Y.; Jackson, B.; Nixon, A.; Schulze, B.; Tanigawa, S-i.; Whiteley, W. | Point-hyperplane frameworks, slider joints, and rigidity preserving transformations | 1703.06844 | J. Combin. Theory. 135 (2019), 44–74. https://doi.org/10.1016/j.jctb.2018.07.008 |
| 2015c39 | Abdi, A.; Pashkovich, K. | Deltas, delta minors and delta free clutters | SIAM J. Discrete Math. 32(3) (2018), 1750–1774. https://doi.org/10.1137/17M1126758 |
|
| 2015c40 | Bérczi, K.; Frank, A. | Supermodularity in unweighted graph optimization I: branchings and matchings | 1608.05722 | Math. Oper. Res. 43(3) (2018), 726–753. https://doi.org/10.1287/moor.2017.0881 |
| 2015c41 | Bérczi, K.; Frank, A. | Supermodularity in unweighted graph optimization II: matroidal term rank augmentation | 1608.05730 | Math. Oper. Res. 43(3) (2018), 754–762. https://doi.org/10.1287/moor.2017.0902 |
| 2015c42 | Bérczi, K.; Frank, A. | Supermodularity in unweighted graph opitimization III: highly-connected digraphs | 1608.05729 | Math. Oper. Res. 43(3) (2018), 763-780. https://doi.org/10.1287/moor.2017.0883 |
| 2015c43 | Könemann, J.; Olver, N.; Pashkovich, K.; Ravi, R.; Swamy, C.; Vygen, J. | On the integrality gap of the prize-collecting Steiner forest LP | 1706.06565 | LIPIcs. 81 (2017), 17:1-17:13. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.17 |
| 2015c44 | Dadush, D.; Végh, L. A.; Zambelli, G. | Rescaled coordinate descent methods for linear programming | Lecture Notes in Computer Science. (2016). https://doi.org/10.1007/978-3-319-33461-5_3 |
|
| 2015c45 | Moriguchi, S.; Murota, K.; Tamura, A.; Tardella, F. | Discrete midpoint convexity | 1708.04579 | Math. Oper. Res. 45(1) (2020), 99–128. https://doi.org/10.1287/moor.2018.0984 |
| 2015c46 | Calinescu, G.; Kortsarz, G.; Nutov, Z. | Improved approximation algorithms for Minimum Power Covering problems | Preprint | Theoret. Comput. Sci. 795 (2019), 285–300. https://doi.org/10.1016/j.tcs.2019.07.010 |
| 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