Integer Programming and Combinatorial Optimization

1. Front Matter

   Pages i-xi

   PDF

2. Identically Self-blocking Clutters

   • Ahmad Abdi, Gérard Cornuéjols, Dabeen Lee

   Pages 1-12

3. Min-Max Correlation Clustering via MultiCut

   • Saba Ahmadi, Samir Khuller, Barna Saha

   Pages 13-26

4. Strong Mixed-Integer Programming Formulations for Trained Neural Networks

   • Ross Anderson, Joey Huchette, Christian Tjandraatmadja, Juan Pablo Vielma

   Pages 27-42

5. Extended Formulations from Communication Protocols in Output-Efficient Time

   • Manuel Aprile, Yuri Faenza

   Pages 43-56

6. Sub-Symmetry-Breaking Inequalities for ILP with Structured Symmetry

   • Pascale Bendotti, Pierre Fouilhoux, Cécile Rottner

   Pages 57-71

7. Intersection Cuts for Polynomial Optimization

   • Daniel Bienstock, Chen Chen, Gonzalo Muñoz

   Pages 72-87

8. Fixed-Order Scheduling on Parallel Machines

   • Thomas Bosman, Dario Frascaria, Neil Olver, René Sitters, Leen Stougie

   Pages 88-100

9. Online Submodular Maximization: Beating 1/2 Made Simple

   • Niv Buchbinder, Moran Feldman, Yuval Filmus, Mohit Garg

   Pages 101-114

10. Improving the Integrality Gap for Multiway Cut

    • Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Vivek Madan

    Pages 115-127

11. \(\ell _1\)-sparsity Approximation Bounds for Packing Integer Programs

    • Chandra Chekuri, Kent Quanrud, Manuel R. Torres

    Pages 128-140

12. A General Framework for Handling Commitment in Online Throughput Maximization

    • Lin Chen, Franziska Eberle, Nicole Megow, Kevin Schewior, Cliff Stein

    Pages 141-154

13. Lower Bounds and a New Exact Approach for the Bilevel Knapsack with Interdiction Constraints

    • Federico Della Croce, Rosario Scatamacchia

    Pages 155-167

14. On Friedmann’s Subexponential Lower Bound for Zadeh’s Pivot Rule

    • Yann Disser, Alexander V. Hopp

    Pages 168-180

15. Tight Approximation Ratio for Minimum Maximal Matching

    • Szymon Dudycz, Mateusz Lewandowski, Jan Marcinkowski

    Pages 181-193

16. Integer Programming and Incidence Treedepth

    • Eduard Eiben, Robert Ganian, Dušan Knop, Sebastian Ordyniak, Michał Pilipczuk, Marcin Wrochna

    Pages 194-204

17. A Bundle Approach for SDPs with Exact Subgraph Constraints

    • Elisabeth Gaar, Franz Rendl

    Pages 205-218

18. Dynamic Flows with Adaptive Route Choice

    • Lukas Graf, Tobias Harks

    Pages 219-232

19. The Markovian Price of Information

    • Anupam Gupta, Haotian Jiang, Ziv Scully, Sahil Singla

    Pages 233-246

20. On Perturbation Spaces of Minimal Valid Functions: Inverse Semigroup Theory and Equivariant Decomposition Theorem

    • Robert Hildebrand, Matthias Köppe, Yuan Zhou

    Pages 247-260

This book constitutes the refereed proceedings of the 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019, held in Ann Arbor, MI, USA, in May 2019.

The 33 full versions of extended abstracts presented were carefully reviewed and selected from 114 submissions. The conference is a forum for researchers and practitioners working on various aspects of integer programming and combinatorial optimization. The aim is to present recent developments in theory, computation, and applications in these areas.

• approximation algorithms
• approximation theory
• artificial intelligence
• combinatorial optimization
• computational results
• Computational results
• computer networks
• game theory
• Game theory
• graph theory
• Heuristic methods
• integer programming
• internet
• linear programming
• problem solving
• Scheduling algorithms
• software engineering
• algorithm analysis and problem complexity
• data structures

• École Polytechnique de Montréal, Montreal, Canada

  Andrea Lodi

• University of Michigan, Ann Arbor, USA

  Viswanath Nagarajan

Policies and ethics