Combinatorial Optimization

1. Front Matter

   Pages I-XXI

   PDF

2. Cluster Editing with Vertex Splitting

   • Faisal N. Abu-Khzam, Judith Egan, Serge Gaspers, Alexis Shaw, Peter Shaw

   Pages 1-13

3. Compact MILP Formulations for the p-Center Problem

   • Zacharie Ales, Sourour Elloumi

   Pages 14-25

4. The Next Release Problem: Complexity, Exact Algorithms and Computations

   • José Carlos Almeida Jr., Felipe de C. Pereira, Marina V. A. Reis, Breno Piva

   Pages 26-38

5. Polytope Membership in High Dimension

   • Evangelos Anagnostopoulos, Ioannis Z. Emiris, Vissarion Fisikopoulos

   Pages 39-51

6. Graph Orientation with Splits

   • Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hesam Nikpey, Hirotaka Ono

   Pages 52-63

7. The Stop Number Minimization Problem: Complexity and Polyhedral Analysis

   • Mourad Baïou, Rafael Colares, Hervé Kerivin

   Pages 64-76

8. Maximum Concurrent Flow with Incomplete Data

   • Pierre-Olivier Bauguion, Claudia D’Ambrosio, Leo Liberti

   Pages 77-88

9. Characterising Chordal Contact \(B_0\)-VPG Graphs

   • Flavia Bonomo, María Pía Mazzoleni, Mariano Leonardo Rean, Bernard Ries

   Pages 89-100

10. Approximating the Caro-Wei Bound for Independent Sets in Graph Streams

    • Graham Cormode, Jacques Dark, Christian Konrad

    Pages 101-114

11. The Minimum Rooted-Cycle Cover Problem

    • D. Cornaz, Y. Magnouche

    Pages 115-120

12. Online Firefighting on Trees

    • Pierre Coupechoux, Marc Demange, David Ellison, Bertrand Jouve

    Pages 121-132

13. A Multigraph Formulation for the Generalized Minimum Spanning Tree Problem

    • Ernando Gomes de Sousa, Rafael Castro de Andrade, Andréa Cynthia Santos

    Pages 133-143

14. The Distance Polytope for the Vertex Coloring Problem

    • Bruno Dias, Rosiane de Freitas, Nelson Maculan, Javier Marenco

    Pages 144-156

15. A PTAS for the Time-Invariant Incremental Knapsack Problem

    • Yuri Faenza, Igor Malinovic

    Pages 157-169

16. On Bounded Pitch Inequalities for the Min-Knapsack Polytope

    • Yuri Faenza, Igor Malinović, Monaldo Mastrolilli, Ola Svensson

    Pages 170-182

17. Efficient Algorithms for Measuring the Funnel-Likeness of DAGs

    • Marcelo Garlet Millani, Hendrik Molter, Rolf Niedermeier, Manuel Sorge

    Pages 183-195

18. Jointly Optimizing Replica Placement, Requests Distribution and Server Storage Capacity on Content Distribution Networks

    • Raquel Gerhardt, Tiago Neves, Luis Rangel

    Pages 196-207

19. An Exact Column Generation-Based Algorithm for Bi-objective Vehicle Routing Problems

    • Estèle Glize, Nicolas Jozefowiez, Sandra Ulrich Ngueveu

    Pages 208-218

20. Multi-start Local Search Procedure for the Maximum Fire Risk Insured Capital Problem

    • Maria Isabel Gomes, Lourdes B. Afonso, Nelson Chibeles-Martins, Joana M. Fradinho

    Pages 219-227

This book constitutes the thoroughly refereed post-conference proceedings of the 5th International Symposium on Combinatorial Optimization, ISCO 2018, held in Marrakesh, Marocco, in April 2018. The 35 revised full papers presented in this book were carefully reviewed and selected from 75 submissions. The symposium aims to bring together researchers from all the communities related to combinatorial optimization, including algorithms and complexity, mathematical programming and operations research.

• problem solving
• graph theory
• inter programming
• approximation algorithms
• computational results
• artificial intelligence
• linear programming
• computer networks
• genetic algorithms
• telecommunication networks
• telecommunication traffic
• exact algorithms
• algorithm analysis and problem complexity
• data structures

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

  Jon Lee

• Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti” (IASI), CNR, Rome, Italy

  Giovanni Rinaldi

• LAMSADE, Université Paris-Dauphine, Paris, France

  A. Ridha Mahjoub

Policies and ethics