Universität Bonn

Trimester Program: "Combinatorial Optimization"

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.

Publications

No. Author(s) Title Preprint Publication
2015c01 Gottschalk, C.; Vygen, J. Better s-t-tours by Gao trees 1511.055144 Lecture Notes in Comput. Sci., 9682
https://doi.org/10.1007/978-3-319-33461-5_115
2015c02 Newman, A.; Röglin, H.; Seif, J. The alternating stock size problem and the gasoline puzzle 1511.092596 ACM Transactions on Algorithms. 14(2) 19 (20018), 1 - 23.
https://doi.org/10.1145/31785397
2015c03 Singh, M.; Zenklusen, R. k-trails: recognition, complexity, and approximations 1512.017818 Math. Program. 172 (2018), 169–189.
https://doi.org/10.1007/s10107-017-1113-z9
2015c04 Fujishige, S.; Tanigawa, S.-i. Polynomial combinatorial algorithms for skew-bisubmodular function minimization pdf10 Math. Program. 171(1-2) (2018), 87–114.
https://doi.org/10.1007/s10107-017-1171-211
2015c05 Borgwardt, S.; De Loera, J. A.; Finhold, E. The diameters of transportation polytopes satisfy the Hirsch conjecture 1603.0032512  
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.0458813 SIAM Journal on Computing. 47(4) (2018), 1667 – 1704.
https://doi.org/10.1137/16M106719614
2015c07 Feldmann, A. E.; Könemann, J.; Pashkovich, K.; Sanità, L. Fast approximation algorithms for the generalized survivable network design problem 1604.0704915 ISAAC 2016. 64(33) (2016), 12.
https://doi.org/10.4230/LIPIcs.ISAAC.2016.3316
2015c08 Friggstad, Z.; Könemann, J.; Shadravan, M. A logarithmic integrality gap bound for directed Steiner tree in quasi-bipartite graphs 1604.0813217 SWAT 2016. 53 (2016), 3:1-3:11.
https://doi.org/10.4230/LIPIcs.SWAT.2016.318
2015c09 Könemann, J.; Pashkovich, K.; Toth, J. An elementary integrality proof of Rothblum's stable matching formulation 1605.0442719 Oper. Res. Lett.44(2016), no.6, 754–756.
https://doi.org/10.1016/j.orl.2016.09.01120
2015c10 Sebő, A.; van Zuylen, A. The salesman's improved paths: a 3/2+1/34 approximation 1604.0248621 EEE 57th FOCS. (2016), 118-127.
https://doi.ieeecomputersociety.org/10.1109/FOCS.2016.2122
2015c11 Conforti, M.; Wolsey, L. A. "Facet" separation with one linear program pdf23 Math. Program. 178(1-2) (2019), 361–380.
https://doi.org/10.1007/s10107-018-1299-824
2015c12 Mnich, M.; Williams, V. V.; Végh, L. A. A 7/3-approximation for feedback vertex sets in tournaments 1511.0113725 ESA 2016. 57 (2016), 67:1-67:14.
https://doi.org/10.4230/LIPIcs.ESA.2016.6726
2015c13 Abdi, A.; Cornuéjols, G.; Pashkovich, K. Ideal clutters that do not pack pdf27  Pack. Mathematics of Operations Research. 43(2) (2017), 533-553.
https://doi.org/10.1287/moor.2017.087128
2015c14 Ahmadian, S.; Swamy, C. Approximation algorithms for clustering problems with lower bounds and outliers 1608.0170029 ICALP 2016. 55 (2016), 69:1-69:15.
https://doi.org/10.4230/LIPIcs.ICALP.2016.6930
2015c15 Fiorini, S.; Huynh, T.; Joret, G.; Pashkovich, K. Smaller extended formulations for the spanning tree polytope of bounded-genus graphs 1604.0797631 Discrete Comput. Geom. 57(3) (2017), 757–761.
https://doi.org/10.1007/s00454-016-9852-932
2015c16 Pashkovich, K. Every rational polyhedron has finite split rank: new proof 1606.0581133  
2015c17 Olver, N.; Végh, L. A. A simpler and faster strongly polynomial algorithm for generalized flow maximization 1611.0177834 Journal of the ACM (JACM). 67(2) 10 (2020), 1 – 26.
https://doi.org/10.1145/338345435
2015c18 Fortier, Q.; Király, C.; Szigeti, Z.; Tanigawa, S-i. On packing spanning arborescences with matroid constraint link36, pdf37 J. Graph Theory. 93(2) (2020), 230–252.
https://doi.org/10.1002/jgt.2248438
2015c19 Bazzi, A.; Fiorini, S.; Huang, S.; Svensson, O. Small extended formulation for knapsack cover inequalities from monotone circuits 1609.0373739 Theory Comput. 14(14) (2018), 29.
https://doi.org/10.4086/toc.2018.v014a01440
2015c20 Dadush, D.; Regev, O. Towards strong reverse Minkowski-type inequalities for lattices 1606.0691341 FOCS 2016. (2016), 447-456.
https://doi.org/10.1109/FOCS.2016.5542
2015c21 Dadush, D.; Végh, L. A.; Zambelli, G. Rescaling algorithms for linear programming - part I: conic feasibility 1611.0642743  
2015c22 van Zuylen, A. Improved approximations for cubic and cubic bipartite TSP 1507.0712144 Math. Program. 172(1-2) (2018), 399–413.
https://doi.org/10.1007/s10107-017-1211-y45
2015c23 Jackson, B.; Nixon, A. Global rigidity of generic frameworks on concentric cylinders 1610.0775546  J. Combin. Theory Ser. 139 (2019), 193–229.
https://doi.org/10.1016/j.jctb.2019.03.00247
2015c24 Panageas, I.; Piliouras, G. Gradient descent only converges to minimizers: non-isolated critical points and invariant regions 1605.0040548 ITCS 2017. 67 (2017), 2:1-2:12.
https://doi.org/10.4230/LIPIcs.ITCS.2017.249
2015c25 Mehta, R.; Panageas, I.; Piliouras, G.; Tetali, P.; Vazirani, V. V. Mutation, sexual reproduction and survival in dynamic environments 1511.0140950 ITCS 2017. 67 (2017), 16:1-16:29.
https://doi.org/10.4230/LIPIcs.ITCS.2017.1651
2015c26 Chandrasekaran, K.; Gottschalk, C.; Könemann, J.; Peis, B.; Schmand, D.; Wierz, A. Additive stabilizers for unstable graphs 1608.0679752 Discrete Optim.31 (2019), 56–78.
https://doi.org/10.1016/j.disopt.2018.08.00353
2015c27 Annamalai, C. Finding perfect matchings in bipartite hypergraphs 1509.0700754 Combinatorica. 38 (2018), 1285–1307.
https://doi.org/10.1007/s00493-017-3567-255
2015c28 Chakrabarty, D.; Lee, Y. T.; Sidford, A.; Wong, Sam C-w. Subquadratic submodular function minimization 1610.0980056 STOC 2017. (2017, 1220 – 1231.
https://doi.org/10.1145/3055399.305541957
2015c29 Lee, J.; Skipper, D. Virtuous smoothing for global optimization 1605.0522158 J. Global Optim. 69(3) (2017), 677–697.
https://doi.org/10.1007/s10898-017-0533-x59
2015c30 Moriguchi, S.; Murota, K.; Tamura, A.; Tardella, F. Scaling, proximity, and optimization of integrally convex functions 1703.1070560 Math. Program.175(1-2) (2019), 119–154.
https://doi.org/10.1007/s10107-018-1234-z61
2015c31 Connelly, R.; Gortler, S. J.; Theran, L. Generic global and universal rigidity 1604.0747562  
2015c32 Chekuri, C.; Xu, C. Computing minimum cuts in hypergraphs 1607.0868263 Symposium on Discrete Algorithms. (2017), 1085 – 1100.
https://doi.org/10.1137/1.9781611974782.7064
2015c33 Chekuri, C. Some open problems in element-connectivity pdf65  
2015c34 Kaszanitzky, V. E.; Schulze, B.; Tanigawa, S-i. Global rigidity of periodic graphs under fixed-lattice representations 1612.0137966 J. Combin. Theory Ser. 146 (2021), 176–218.
https://doi.org/10.1016/j.jctb.2020.09.00967
2015c35 Arulselvan, A.; Cseh, Á.; Groß, M.; Manlove, D. F.; Matuschke, J. Matchings with lower quotas: algorithms and complexity 1412.032568 Algorithmica. 80(1) (2018), 185–208.
https://doi.org/10.1007/s00453-016-0252-669
2015c36 Iwamasa, Y.; Murota, K.; Zivny, S. Discrete convexity in joint winner property 1701.0764570 Discrete Optim. 28 (2018), 78–88.
https://doi.org/10.1016/j.disopt.2018.01.00171
2015c37 Palaiopanos, G.; Panageas, I.; Piliouras, G. Multiplicative weights update with constant step-size in congestion games: convergence, limit cycles and chaos 1703.0113872  NIPS'17. (2017), 5874 – 5884.
https://dl.acm.org/doi/10.5555/3295222.329533773
2015c38 Eftekhari, Y.; Jackson, B.; Nixon, A.; Schulze, B.; Tanigawa, S-i.; Whiteley, W. Point-hyperplane frameworks, slider joints, and rigidity preserving transformations 1703.0684474 J. Combin. Theory. 135 (2019), 44–74.
https://doi.org/10.1016/j.jctb.2018.07.00875
2015c39 Abdi, A.; Pashkovich, K. Deltas, delta minors and delta free clutters pdf76 SIAM J. Discrete Math. 32(3) (2018), 1750–1774.
https://doi.org/10.1137/17M112675877
2015c40 Bérczi, K.; Frank, A. Supermodularity in unweighted graph optimization I: branchings and matchings 1608.0572278 Math. Oper. Res. 43(3) (2018), 726–753.
https://doi.org/10.1287/moor.2017.088179
2015c41 Bérczi, K.; Frank, A. Supermodularity in unweighted graph optimization II: matroidal term rank augmentation 1608.0573080 Math. Oper. Res. 43(3) (2018), 754–762.
https://doi.org/10.1287/moor.2017.090281
2015c42 Bérczi, K.; Frank, A. Supermodularity in unweighted graph opitimization III: highly-connected digraphs 1608.0572982 Math. Oper. Res. 43(3) (2018), 763-780.
https://doi.org/10.1287/moor.2017.088383
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.0656584 LIPIcs. 81 (2017), 17:1-17:13.
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.1785
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_386
2015c45 Moriguchi, S.; Murota, K.; Tamura, A.; Tardella, F. Discrete midpoint convexity 1708.0457987 Math. Oper. Res. 45(1) (2020), 99–128.
https://doi.org/10.1287/moor.2018.098488
2015c46 Calinescu, G.; Kortsarz, G.; Nutov, Z. Improved approximation algorithms for Minimum Power Covering problems Preprint89 Theoret. Comput. Sci. 795 (2019), 285–300.
https://doi.org/10.1016/j.tcs.2019.07.01090

Participants

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.

Poster TP_2015_09.jpg
© HIM

Links

  1. https://www.mathematics.uni-bonn.de/him/programs/past/tp_2015_09#pubs
  2. https://www.mathematics.uni-bonn.de/en/programs/assets/report-tp_2015_09.pdf
  3. https://www.mathematics.uni-bonn.de/him/programs/past/tp_2015_09#part
  4. http://arxiv.org/abs/1511.05514
  5. https://doi.org/10.1007/978-3-319-33461-5_11
  6. http://arxiv.org/abs/1511.09259
  7. https://doi.org/10.1145/3178539
  8. http://arxiv.org/abs/1512.01781
  9. https://doi.org/10.1007/s10107-017-1113-z
  10. http://www.kurims.kyoto-u.ac.jp/preprint/file/RIMS1837.pdf
  11. https://doi.org/10.1007/s10107-017-1171-2
  12. http://arxiv.org/abs/1603.00325
  13. http://arxiv.org/abs/1502.04588
  14. https://doi.org/10.1137/16M1067196
  15. http://arxiv.org/abs/1604.07049
  16. https://doi.org/10.4230/LIPIcs.ISAAC.2016.33
  17. http://arxiv.org/abs/1604.08132
  18. https://doi.org/10.4230/LIPIcs.SWAT.2016.3
  19. http://arxiv.org/abs/1605.04427
  20. https://doi.org/10.1016/j.orl.2016.09.011
  21. http://arxiv.org/abs/1604.02486
  22. https://doi.ieeecomputersociety.org/10.1109/FOCS.2016.21
  23. http://alfresco.uclouvain.be/alfresco/service/guest/streamDownload/workspace/SpacesStore/b6ca1ad9-a17f-4249-918e-81b221038501/coredp2016_21web.pdf?guest=true
  24. https://doi.org/10.1007/s10107-018-1299-8
  25. http://arxiv.org/abs/1511.01137
  26. https://doi.org/10.4230/LIPIcs.ESA.2016.67
  27. http://www.math.uwaterloo.ca/~a3abdi/papers/idealmnp.pdf
  28. https://doi.org/10.1287/moor.2017.0871
  29. http://arxiv.org/abs/1608.01700
  30. https://doi.org/10.4230/LIPIcs.ICALP.2016.69
  31. http://arxiv.org/abs/1604.07976
  32. https://doi.org/10.1007/s00454-016-9852-9
  33. http://arxiv.org/abs/1606.05811
  34. http://arxiv.org/abs/1611.01778
  35. https://doi.org/10.1145/3383454
  36. https://www.cs.elte.hu/egres/www/tr-16-18
  37. https://www.cs.elte.hu/egres/tr/egres-16-18.pdf
  38. https://doi.org/10.1002/jgt.22484
  39. http://arxiv.org/abs/1609.03737
  40. https://doi.org/10.4086/toc.2018.v014a014
  41. http://arxiv.org/abs/1606.06913
  42. https://doi.org/10.1109/FOCS.2016.55
  43. http://arxiv.org/abs/1611.06427
  44. http://arxiv.org/abs/1507.07121
  45. https://doi.org/10.1007/s10107-017-1211-y
  46. http://arxiv.org/abs/1610.07755
  47. https://doi.org/10.1016/j.jctb.2019.03.002
  48. http://arxiv.org/abs/1605.00405
  49. https://doi.org/10.4230/LIPIcs.ITCS.2017.2
  50. http://arxiv.org/abs/1511.01409
  51. https://doi.org/10.4230/LIPIcs.ITCS.2017.16
  52. http://arxiv.org/abs/1608.06797
  53. https://doi.org/10.1016/j.disopt.2018.08.003
  54. http://arxiv.org/abs/1509.07007
  55. https://doi.org/10.1007/s00493-017-3567-2
  56. http://arxiv.org/abs/1610.09800
  57. https://doi.org/10.1145/3055399.3055419
  58. http://arxiv.org/abs/1605.05221
  59. https://doi.org/10.1007/s10898-017-0533-x
  60. http://arxiv.org/abs/1703.10705
  61. https://doi.org/10.1007/s10107-018-1234-z
  62. http://arxiv.org/abs/1604.07475
  63. http://arxiv.org/abs/1607.08682
  64. https://doi.org/10.1137/1.9781611974782.70
  65. http://chekuri.cs.illinois.edu/papers/elem-connectivity-open-probs.pdf
  66. http://arxiv.org/abs/1612.01379
  67. https://doi.org/10.1016/j.jctb.2020.09.009
  68. http://arxiv.org/abs/1412.0325
  69. https://doi.org/10.1007/s00453-016-0252-6
  70. http://arxiv.org/abs/1701.07645
  71. https://doi.org/10.1016/j.disopt.2018.01.001
  72. http://arxiv.org/abs/1703.01138
  73. https://dl.acm.org/doi/10.5555/3295222.3295337
  74. http://arxiv.org/abs/1703.06844
  75. https://doi.org/10.1016/j.jctb.2018.07.008
  76. http://www.math.uwaterloo.ca/~a3abdi/papers/deltas.pdf
  77. https://doi.org/10.1137/17M1126758
  78. http://arxiv.org/abs/1608.05722
  79. https://doi.org/10.1287/moor.2017.0881
  80. http://arxiv.org/abs/1608.05730
  81. https://doi.org/10.1287/moor.2017.0902
  82. http://arxiv.org/abs/1608.05729
  83. https://doi.org/10.1287/moor.2017.0883
  84. http://arxiv.org/abs/1706.06565
  85. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.17
  86. https://doi.org/10.1007/978-3-319-33461-5_3
  87. http://arxiv.org/abs/1708.04579
  88. https://doi.org/10.1287/moor.2018.0984
  89. http://www.cs.iit.edu/~calinesc/power_cover.pdf
  90. https://doi.org/10.1016/j.tcs.2019.07.010
  91. https://www.mathematics.uni-bonn.de/him/programs/past/tp_2015_09#start