Combinatorial Optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers

Front Matter....Pages -
Structure Theorems for Optimum Hyperpaths in Directed Hypergraphs....Pages 1-14
Branch-and-Price Guided Search....Pages 15-18
The New Faces of Combinatorial Optimization....Pages 19-23
Models and Algorithms for the Train Unit Assignment Problem....Pages 24-35
The Minimum Stabbing Triangulation Problem: IP Models and Computational Evaluation....Pages 36-47
Orbital Shrinking....Pages 48-58
Using Symmetry to Optimize Over the Sherali-Adams Relaxation....Pages 59-70
A Second-Order Cone Programming Approximation to Joint Chance-Constrained Linear Programs....Pages 71-80
Semidefinite Relaxations for Mixed 0-1 Second-Order Cone Program....Pages 81-92
The Non-Disjoint m -Ring-Star Problem: Polyhedral Results and SDH/SONET Network Design....Pages 93-104
The Uncapacitated Asymmetric Traveling Salesman Problem with Multiple Stacks....Pages 105-116
Polyhedral Analysis and Branch-and-Cut for the Structural Analysis Problem....Pages 117-128
Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols....Pages 129-140
An Algebraic Approach to Symmetric Extended Formulations....Pages 141-152
Dual Consistent Systems of Linear Inequalities and Cardinality Constrained Polytopes....Pages 153-164
Minimum Ratio Cover of Matrix Columns by Extreme Rays of Its Induced Cone....Pages 165-177
Gap Inequalities for the Max-Cut Problem: A Cutting-Plane Algorithm....Pages 178-188
Fast Separation Algorithms for Three-Index Assignment Problems....Pages 189-200
On the Hop Constrained Steiner Tree Problem with Multiple Root Nodes....Pages 201-212
Theoretical Investigation of Aggregation in Pseudo-polynomial Network-Flow Models....Pages 213-224
On Solving the Rooted Delay- and Delay-Variation-Constrained Steiner Tree Problem....Pages 225-236
A Parallel Lagrangian Relaxation Algorithm for the Min-Degree Constrained Minimum Spanning Tree Problem....Pages 237-248
Layered Formulation for the Robust Vehicle Routing Problem with Time Windows....Pages 249-260
Models and Algorithms for Robust Network Design with Several Traffic Scenarios....Pages 261-272
Aircraft Sequencing Problems via a Rolling Horizon Algorithm....Pages 273-284
On the Solution of a Graph Partitioning Problem under Capacity Constraints....Pages 285-296
Sum-Max Graph Partitioning Problem....Pages 297-308
The Packing Coloring Problem for (q,q-4) Graphs....Pages 309-319
Selective Graph Coloring in Some Special Classes of Graphs....Pages 320-331
Graph Orientations Optimizing the Number of Light or Heavy Vertices....Pages 332-343
Constrained Matching Problems in Bipartite Graphs....Pages 344-355
The Gram Dimension of a Graph....Pages 356-367
Exploiting a Hypergraph Model for Finding Golomb Rulers....Pages 368-379
Counting Homomorphisms via Hypergraph-Based Structural Restrictions....Pages 380-391
Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines....Pages 392-403
Differential Approximation of the Multiple Stacks TSP....Pages 404-415
Completion Time Scheduling and the WSRPT Algorithm....Pages 416-426
Two-Agent Scheduling on an Unbounded Serial Batching Machine....Pages 427-438
Second-Price Ad Auctions with Binary Bids and Markets with Good Competition....Pages 439-450
Towards Minimizing k -Submodular Functions....Pages 451-462
Recognition Algorithms for Binary Signed-Graphic Matroids....Pages 463-474
Back Matter....Pages -