September 6 - December 17, 2021
Organizers: Daniel Dadush, Jesper Nederlof, Neil Olver, Laura Sanità, László Végh
Description: Discrete optimization is an extremely active area with increasingly deepening connections to other areas of mathematics. We aim to take classical areas of discrete optimization in modern directions, and to foster the use of techniques from other areas.
Associated Events:
Summer School on modern directions in discrete optimization (September 13 - 17, 2021)
Workshop: Tropical geometry and the geometry of linear programming (September 20 - 24, 2021)
Workshop: Continuous approaches to discrete optimization (October 11 - 15, 2021)
Workshop: Approximation and relaxation (November 15 - 19, 2021)
Workshop: Parametrized complexity and discrete optimization (December 6 - 10, 2021)
© HIM
No. |
Author(s) |
Title |
Preprint |
Publication |
| 2021c01 | Abdi, A.; Cornuejols, G.; Zlatin, M. | On packing dijoins in digraphs and weighted digraphs | 2202.00392 | SIAM Journal on Discrete Mathematics (2023) Vol. 37, Iss. 4 https://doi.org/10.1137/22M1506511 |
| 2021c02 | Allamigeon, X.; Dadush, D.; Loho, G.; Natura, B.; Végh, L.A. | Interior point methods are not worse than simplex | 2206.08810 | Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), 267-277, https://doi.org/10.1109/FOCS54457.2022.00032 |
| 2021c03 | Allamigeon, X.; Gaubert, S.; Vandame, N. | No self-concordant barrier interior point method is strongly polynomial | 2201.02186 | Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (2022). 515–528 https://doi.org/10.1145/3519935.3519997 |
| 2021c04 | Bérczi, K.; Hoang, H.P.; Tóthmérész, L. | On approximating the rank of graph divisors | 2206.09662 |
Discrete Mathematics (2023), 346 (9): 113528, https://doi.org/10.1016/j.disc.2023.113528 |
| 2021c05 | Black, A.E. | Small shadows of lattice polytopes | 2204.09129 |
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), 1669 - 1679, https://doi.org/10.1137/1.9781611977554.ch6 |
| 2021c06 | Bodlaender, H.L.; Groenland, C.; Jacob, H.; Pilipczuk, M.; Pilipczuk, M.; | On the complexity of problems on tree-structured graphs | 2206.11828 |
Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, 6:1-6:17, https://doi.org/10.4230/LIPIcs.IPEC.2022.6 |
| 2021c07 | Bonnet, G.; Huiberts, S.; Dadush, D.; Grupel, U.; Livshyts, G. | Asymptotic bounds on the combinatorial diameter of random polytopes | 2112.13027 |
Proceedings of the 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, 18:1-18:15, https://doi.org/10.4230/LIPIcs.SoCG.2022.18 |
| 2021c08 | Caoduro, M.; Cslovjecsek, J.; Pilipczuk, M.; Wegrzycki, K. | Independence number of intersection graphs of axis-parallel segments | 2205.15189 | Journal of Computational Geometry 14(1) (2023), https://doi.org/10.20382/jocg.v14i1a5 |
| 2021c09 | Chakrabarty, D.; Graur, A.; Jiang, H.; Sidford, A. | Improved lower bounds for submodular function minimization | Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), 245-254, https://doi.org/10.1109/FOCS54457.2022.00030 | |
| 2021c10 | Chalermsook, P.; Fomin, F.; Hamm, T.; Korhonen, T.; Nederlof, J.; Orgo, L. | Polynomial-time approximation of independent set parameterized by treewidth | 2307.01341 | Proceedings of the 31st Annual European Symposium on Algorithms (ESA 2023), Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, 33:1-33:13, https://doi.org/10.4230/LIPIcs.ESA.2023.33 |
| 2021c11 | Chandrasekaran, K.; Chekuri, C.; Fiorini, S.; Kulkarni, S.; Weltge, S. | Polyhedral aspects of feedback vertex set and pseudoforest deletion set | 2303.12850 |
|
| 2021c12 | Cslovjecsek, J.; Pilipczuk, M.; Wegrzycki, K. | Parameterized approximation for maximum weight independent set of rectangles and segments | 2212.01620 |
|
| 2021c13 | Dadush, D.; Koh, Z.K.; Natura, B.; Végh, L.A. | On circuit diameter bounds via circuit imbalances | Integer Programming and Combinatorial Optimization (IPCO 2022), Lecture Notes in Computer Science, vol 13265, Springer, Cham., https://doi.org/10.1007/978-3-031-06901-7_11 | |
| 2021c14 | Huang, C.-C.; Chalermsook, P.; Nanongkai, D.; Saranurak, T.; Sukprasert, P.; Yingchareonthawornchai, S. | Approximating k-edge connected spanning subgraphs via a near-linear time LP solver | 2205.14978 |
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, 37:1-37:20, https://doi.org/10.4230/LIPIcs.ICALP.2022.37 |
| 2021c15 | Hunkenschröder, C.; Pokutta, S.; Weismantel, R. | Minimizing a low-dimensional convex function over a high-dimensional cube | SIAM Journal on Optimization (2023) Vol. 33, Iss. 2, https://doi.org/10.1137/22M1489988 | |
| 2021c16 | Husić, E.; Koh, Z.K.; Loho, G., Végh, L.A. | On the correlation gap of matroids | 2209.09896 | Integer Programming and Combinatorial Optimization (IPCO 2023), Lecture Notes in Computer Science, vol 13904. Springer, Cham., https://doi.org/10.1007/978-3-031-32726-1_15 |
| 2021c17 | Joswig, M.; Loho, G.; Luber D.; Alberto Olarte, J. | Generalized Permutahedra and Positive Flag Dressians | 2111.13676 |
International Mathematics Research Notices (2023), Issue 19, 16748–16777, https://doi.org/10.1093/imrn/rnac349 |
| 2021c18 | Klein, K.-M.; Polak, A.; Rohwedder, L. | On minimizing tardy processing time, max-min skewed convolution, and triangular structured ilps | 2211.05053 |
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), 2947-2960, https://doi.org/10.1137/1.9781611977554.ch112 |
| 2021c19 | Klein, N.; Olver, N. | Thin trees for laminar families | 2304.07674 | Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), 50-59, https://doi.org/10.1109/FOCS57990.2023.00011 |
| 2021c20 | Loho, G.; Skomra, M. | Signed tropical halfspaces and convexity | 2206.13919 |
|
| 2021c21 | Nederlof, J.; Pilipczuk, M.; Wegrzycki, K. | Bounding generalized coloring numbers of planar graphs using coin models | 2201.09340 | The Electronic Journal of Combinatorics (2023), 20(3), https://doi.org/10.37236/11095 |
| 2021c22 | Olver, N.; Sering, L.; Vargas Koch, L. | Convergence of approximate and packet routing equilibria to nash flows over time | 2402.04935 |
Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), 123-133, https://doi.org/10.1109/FOCS57990.2023.00016 |
| 2021c23 | Saranurak, T.; Yingchareonthawornchai, S. | Deterministic small vertex connectivity in almost linear time | 2210.13739 |
Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), 789-800, https://doi.org/10.1109/FOCS54457.2022.00080 |
| 2021c24 | Traub, V.; Zenklusen, R. | A (1.5+ℇ)-approximation algorithm for weighted connectivity augmentation | 2209.07860 |
Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), 1820–1833, https://doi.org/10.1145/3564246.3585122 |
| 2021c25 | Van den Brand, J.; Gao, Y., Jambulapati, A.; Lee, Y.T.; Lio, Y.P.; Peng, R.; Sidforf, A. | Faster maxflow via improved dynamic spectral vertex sparsifiers | 2112.00722 |
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), 543–556, https://doi.org/10.1145/3519935.3520068 |
| 2021c26 | Cslovjecsek, J.; Pilipczuk, M.; Węgrzycki, K. | A polynomial-time OPTɛ-approximation algorithm for maximum independent set of connected subgraphs in a planar graph | 2310.20325 |
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), 625-638, https://doi.org/10.1137/1.9781611977912.2 |
| 2021c27 | Cslovjecsek, J.; Koutecký, M.; Lassota, A.; Pilipczuk, M.; Polak, A. | Parameterized algorithms for block-structured integer programs with large entries |
2311.01890 |
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), 740–751, https://doi.org/10.1137/1.9781611977912.2 |
| 2021c28 | Heimann, S.; Hoang, H.P.; Hougardy, S. | The k-Opt algorithm for the Traveling Salesman Problem has exponential running time for k≥5 | 2402.07061 |
Name |
Affiliation |
| Fateme Abbasi | University of Wroclaw |
| Ahmad Abdi | London School of Economics and Political Science |
| Xavier Allamigeon | INRIA and Ecole Polytechnique |
| Alexander Black | UC Davis |
| Jan van den Brand | KTH Royal Institute of Technology |
| Marie-Charlotte Brandenburg | Max-Planck-Institut für Mathematik in den Naturwissenschaften |
| Kristóf Bérczi | Eötvös Loránd University |
| Marco Caoduro | UGA - GSCOP Laboratory |
| Deeparnab Chakrabarty | Dartmouth College |
| Parinya Chalermsook | Department of Computer Science Aalto University |
| Parinya Chalermsook | Department of Computer Science Aalto University |
| Karthekeyan Chandrasekaran | University of Illinois, Urbana-Champaign |
| Gerard Cornuejols | Carnegie Mellon University |
| Jana Cslovjecsek | EPFL |
| Daniel Dadush | CWI |
| Jesus De Loera | University of California |
| Sally Dong | University of Washington |
| Anne Driemel | Universität Bonn |
| Franziska Eberle | LSE London |
| Fritz Eisenbrand | EPFL |
| Andreas Feldmann | Charles University |
| Samuel Fiorini | Université libre de Bruxelles |
| Fedor Fomin | Institutt for informatikk |
| Michel Goemans | MIT |
| Fabrizio Grandoni | IDSIA, USI-SUPSI |
| Carla Groenland | Utrecht University |
| Stephan Held | Universität Bonn |
| Christoph Hertrich | Technische Universität Berlin |
| Hung Hoang | ETH Zurich |
| Stefan Hougardy | Universität Bonn |
| Sophie Huiberts | Centrum Wiskunde & Informatica |
| Christoph Hunkenschröder | TU Berlin |
| Haotian Jiang | University of Washington |
| Michael Joswig | TU Berlin |
| Thomas Kesselheim | Universität Bonn |
| Kim-Manuel Klein | University of Kiel |
| Nathan Klein | University of Washington |
| Zhuan Khye Koh | London School of Economics and Political Science |
| Tuukka Korhonen | University of Bergen |
| Rasmus Kyng | ETH Zurich |
| Alexandra Lassota | EPFL |
| Roie Levin | Carnegie Mellon University |
| Georg Loho | University of Twente |
| Nicole Megow | University of Bremen |
| Matthias Mnich | Hamburg University of Technology |
| Bento Natura | London School of Economics and Political Science |
| Jesper Nederlof | Utrecht University |
| Alantha Newman | Laboratoire G-SCOP |
| Martin Nägele | Universität Bonn |
| Neil Olver | LSE London |
| Britta Peis | RWTH Aachen University |
| Michał Pilipczuk | University of Warsaw |
| Sebastian Pokutta | Zuse Institut Berlin |
| Adam Polak | EPFL |
| Thomas Rothvoss | University of Washington |
| Heiko Röglin | Universität Bonn |
| Vibha Sahlot | Charles University |
| Laura Sanità | TU Eindhoven |
| András Sebő | CNRS, Laboratoire G-SCOP, UNIV Grenoble-Alpes |
| Aaron Sidford | Stanford Uniiversity |
| Karl Stickler | London School of Economics and Political Science |
| Ola Svensson | EPFL |
| Céline Swennenhuis | Eindhoven University of Technology |
| Vera Traub | ETH |
| Thorben Tröbst | University of California, Irvine |
| Laura Vargas Koch | ETH Zürich |
| Jens Vygen | Universität Bonn |
| László Végh | LSE London |
| Karol Wegrzycki | Saarland University and Max Planck Institute for Informatics |
| Stefan Weltge | Technische Universität München |
| Stephen Wright | University of Wisconsin-Madison |
| Fei Wu | KU Leuven |
| Sorrachai Yingchareonthawornchai | Aalto University |
| Rico Zenklusen | ETH Zurich |
© HIM