Integer Programming and Combinatorial Optimization

1. Front Matter

   PDF

2. The Cycling Property for the Clutter of Odd st-Walks

   • Ahmad Abdi, Bertrand Guenin

   Pages 1-12

3. On Simplex Pivoting Rules and Complexity Theory

   • Ilan Adler, Christos Papadimitriou, Aviad Rubinstein

   Pages 13-24

4. A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts

   • Hassene Aissi, A. Ridha Mahjoub, S. Thomas McCormick, Maurice Queyranne

   Pages 25-36

5. Integer Programs with Prescribed Number of Solutions and a Weighted Version of Doignon-Bell-Scarf’s Theorem

   • Iskander Aliev, Jesús A. De Loera, Quentin Louveaux

   Pages 37-51

6. Centrality of Trees for Capacitated k-Center

   • Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, Ola Svensson

   Pages 52-63

7. Sequence Independent, Simultaneous and Multidimensional Lifting of Generalized Flow Covers for the Semi-Continuous Knapsack Problem with Generalized Upper Bounds Constraints

   • Alejandro Angulo, Daniel Espinoza, Rodrigo Palma

   Pages 64-75

8. On the Unique-Lifting Property

   • Gennadiy Averkov, Amitabh Basu

   Pages 76-87

9. Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs

   • Mourad Baïou, Francisco Barahona

   Pages 88-101

10. n-Step Cycle Inequalities: Facets for Continuous n-Mixing Set and Strong Cuts for Multi-Module Capacitated Lot-Sizing Problem

    • Manish Bansal, Kiavash Kianfar

    Pages 102-113

11. On the Adaptivity Gap of Stochastic Orienteering

    • Nikhil Bansal, Viswanath Nagarajan

    Pages 114-125

12. A Utility Equivalence Theorem for Concave Functions

    • Anand Bhalgat, Sanjeev Khanna

    Pages 126-137

13. Network Improvement for Equilibrium Routing

    • Umang Bhaskar, Katrina Ligett, Leonard J. Schulman

    Pages 138-149

14. Finding Small Stabilizers for Unstable Graphs

    • Adrian Bock, Karthekeyan Chandrasekaran, Jochen Könemann, Britta Peis, Laura Sanità

    Pages 150-161

15. The Triangle Splitting Method for Biobjective Mixed Integer Programming

    • Natashia Boland, Hadi Charkhgard, Martin Savelsbergh

    Pages 162-173

16. Cut Generation through Binarization

    • Pierre Bonami, François Margot

    Pages 174-185

17. A \(\frac{5}{4}\)-Approximation for Subcubic 2EC Using Circulations

    • Sylvia Boyd, Yao Fu, Yu Sun

    Pages 186-197

18. Box-Constrained Mixed-Integer Polynomial Optimization Using Separable Underestimators

    • Christoph Buchheim, Claudia D’Ambrosio

    Pages 198-209

19. Submodular Maximization Meets Streaming: Matchings, Matroids, and More

    • Amit Chakrabarti, Sagar Kale

    Pages 210-221

20. The All-or-Nothing Flow Problem in Directed Graphs with Symmetric Demand Pairs

    • Chandra Chekuri, Alina Ene

    Pages 222-233

This book constitutes the refereed proceedings of the 17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014, held in Bonn, Germany, in June 2014. The 34 full papers presented were carefully reviewed and selected from 143 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. The scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integer programming and combinatorial optimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.

• approximation algorithms
• combinatorial optimization
• computational complexity
• integer programming
• linear programming
• algorithm analysis and problem complexity

• Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA

  Jon Lee

• Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany

  Jens Vygen

Policies and ethics