Integer Programming and Combinatorial Optimization: 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings

✍ Scribed by Jon Lee, Jens Vygen (eds.)

• Publisher: Springer International Publishing
• Year: 2014
• Tongue: English
• Leaves: 429
• Series: Lecture Notes in Computer Science 8494 Theoretical Computer Science and General Issues
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Front Matter....Pages -
The Cycling Property for the Clutter of Odd  st -Walks....Pages 1-12
On Simplex Pivoting Rules and Complexity Theory....Pages 13-24
A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts....Pages 25-36
Integer Programs with Prescribed Number of Solutions and a Weighted Version of Doignon-Bell-Scarf’s Theorem....Pages 37-51
Centrality of Trees for Capacitated k -Center....Pages 52-63
Sequence Independent, Simultaneous and Multidimensional Lifting of Generalized Flow Covers for the Semi-Continuous Knapsack Problem with Generalized Upper Bounds Constraints....Pages 64-75
On the Unique-Lifting Property....Pages 76-87
Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs....Pages 88-101
n -Step Cycle Inequalities: Facets for Continuous n -Mixing Set and Strong Cuts for Multi-Module Capacitated Lot-Sizing Problem....Pages 102-113
On the Adaptivity Gap of Stochastic Orienteering....Pages 114-125
A Utility Equivalence Theorem for Concave Functions....Pages 126-137
Network Improvement for Equilibrium Routing....Pages 138-149
Finding Small Stabilizers for Unstable Graphs....Pages 150-161
The Triangle Splitting Method for Biobjective Mixed Integer Programming....Pages 162-173
Cut Generation through Binarization....Pages 174-185
A $\frac{5}{4}$ -Approximation for Subcubic 2EC Using Circulations....Pages 186-197
Box-Constrained Mixed-Integer Polynomial Optimization Using Separable Underestimators....Pages 198-209
Submodular Maximization Meets Streaming: Matchings, Matroids, and More....Pages 210-221
The All-or-Nothing Flow Problem in Directed Graphs with Symmetric Demand Pairs....Pages 222-233
Reverse Split Rank....Pages 234-248
Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines....Pages 249-260
How Good Are Sparse Cutting-Planes?....Pages 261-272
Short Tours through Large Linear Forests....Pages 273-284
Linear Programming Hierarchies Suffice for Directed Steiner Tree....Pages 285-296
An Improved Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties....Pages 297-308
Simple Extensions of Polytopes....Pages 309-320
Lower Bounds on the Sizes of Integer Programs without Additional Variables....Pages 321-332
On the Configuration LP for Maximum Budgeted Allocation....Pages 333-344
Two-Term Disjunctions on the Second-Order Cone....Pages 345-356
Coupled and k -Sided Placements: Generalizing Generalized Assignment....Pages 357-368
A Unified Algorithm for Degree Bounded Survivable Network Design....Pages 369-380
Scheduling and Fixed-Parameter Tractability....Pages 381-392
Improved Branch-Cut-and-Price for Capacitated Vehicle Routing....Pages 393-403
Claw-Free t -Perfect Graphs Can Be Recognised in Polynomial Time....Pages 404-415
Back Matter....Pages -

✦ Subjects

Numeric Computing; Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science