Combinatorial Optimization

1. Front Matter

   PDF

2. Invited Talks

   1. Structure Theorems for Optimum Hyperpaths in Directed Hypergraphs

      • Giorgio Ausiello, Giuseppe F. Italiano, Luigi Laura, Umberto Nanni, Fabiano Sarracco

      Pages 1-14

   2. Branch-and-Price Guided Search

      • Mike Hewitt, George L. Nemhauser, Martin Savelsbergh

      Pages 15-18

   3. The New Faces of Combinatorial Optimization

      • Christos H. Papadimitriou

      Pages 19-23

   4. Models and Algorithms for the Train Unit Assignment Problem

      • Valentina Cacchiani, Alberto Caprara, Paolo Toth

      Pages 24-35

3. Contributed Talks

   1. The Minimum Stabbing Triangulation Problem: IP Models and Computational Evaluation

      • Breno Piva, Cid C. de Souza

      Pages 36-47

   2. Orbital Shrinking

      • Matteo Fischetti, Leo Liberti

      Pages 48-58

   3. Using Symmetry to Optimize Over the Sherali-Adams Relaxation

      • James Ostrowski

      Pages 59-70

   4. A Second-Order Cone Programming Approximation to Joint Chance-Constrained Linear Programs

      • Jianqiang Cheng, Céline Gicquel, Abdel Lisser

      Pages 71-80

   5. Semidefinite Relaxations for Mixed 0-1 Second-Order Cone Program

      • Agnès Gorge, Abdel Lisser, Riadh Zorgati

      Pages 81-92

   6. The Non-Disjoint m-Ring-Star Problem: Polyhedral Results and SDH/SONET Network Design

      • Pierre Fouilhoux, Aurélien Questel

      Pages 93-104

   7. The Uncapacitated Asymmetric Traveling Salesman Problem with Multiple Stacks

      • Sylvie Borne, Roland Grappe, Mathieu Lacroix

      Pages 105-116

   8. Polyhedral Analysis and Branch-and-Cut for the Structural Analysis Problem

      • Mathieu Lacroix, A. Ridha Mahjoub, Sébastien Martin

      Pages 117-128

   9. Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols

      • Yuri Faenza, Samuel Fiorini, Roland Grappe, Hans Raj Tiwary

      Pages 129-140

   10. An Algebraic Approach to Symmetric Extended Formulations

       • Gábor Braun, Sebastian Pokutta

       Pages 141-152

   11. Dual Consistent Systems of Linear Inequalities and Cardinality Constrained Polytopes

       • Satoru Fujishige, Jens Maßberg

       Pages 153-164

   12. Minimum Ratio Cover of Matrix Columns by Extreme Rays of Its Induced Cone

       • A. S. Freire, V. Acuña, P. Crescenzi, C. E. Ferreira, V. Lacroix, P. V. Milreu et al.

       Pages 165-177

   13. Gap Inequalities for the Max-Cut Problem: A Cutting-Plane Algorithm

       • Laura Galli, Konstantinos Kaparis, Adam N. Letchford

       Pages 178-188

   14. Fast Separation Algorithms for Three-Index Assignment Problems

       • Trivikram Dokka, Ioannis Mourtos, Frits C. R. Spieksma

       Pages 189-200

   15. On the Hop Constrained Steiner Tree Problem with Multiple Root Nodes

       • Luis Gouveia, Markus Leitner, Ivana Ljubić

       Pages 201-212

This book constitutes the thoroughly refereed post-conference proceedings of the Second International Symposium on Combinatorial Optimization, ISCO 2012, held in Athens, Greece, in April 2012. The 37 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 94 regular and 30 short submissions. They present original research on all aspects of combinatorial optimization, ranging from mathematical foundations and theory of algorithms to computational studies and practical applications.

• algorithms and complexity
• graph problems
• mathematical programming
• networks
• relaxation
• algorithm analysis and problem complexity

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

  A. Ridha Mahjoub, Vangelis Th. Paschos

• Department of Informatics, Athens University of Economics and Business, Athens, Greece

  Vangelis Markakis, Ioannis Milis

Policies and ethics