Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings

Front Matter....Pages I-XIII
On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming....Pages 1-13
Centerpoints: A Link Between Optimization and Convex Geometry....Pages 14-25
Rescaled Coordinate Descent Methods for Linear Programming....Pages 26-37
Approximating Min-Cost Chain-Constrained Spanning Trees: A Reduction from Weighted to Unweighted Problems....Pages 38-49
Max-Cut Under Graph Constraints....Pages 50-62
Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem....Pages 63-76
Intersection Cuts for Bilevel Optimization....Pages 77-88
Exact Algorithms for the Chance-Constrained Vehicle Routing Problem....Pages 89-101
Extended Formulations in Mixed-Integer Convex Programming....Pages 102-113
Better s-t-Tours by Gao Trees....Pages 114-125
Popular Edges and Dominant Matchings....Pages 126-137
Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines....Pages 138-151
Stabilizing Network Bargaining Games by Blocking Players....Pages 152-163
Round-Robin Tournaments Generated by the Circle Method Have Maximum Carry-Over....Pages 164-177
Extreme Functions with an Arbitrary Number of Slopes....Pages 178-189
Minimal Cut-Generating Functions are Nearly Extreme....Pages 190-201
On the Mixed Binary Representability of Ellipsoidal Regions....Pages 202-213
Constant Factor Approximation for ATSP with Two Edge Weights....Pages 214-225
Improved Approximation Algorithms for Hitting 3-Vertex Paths....Pages 226-237
Improved Approximations for Cubic Bipartite and Cubic TSP....Pages 238-249
Valid Inequalities for Separable Concave Constraints with Indicator Variables....Pages 250-261
A Polyhedral Approach to Online Bipartite Matching....Pages 262-274
On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvátal Rank....Pages 275-286
Robust Monotone Submodular Function Maximization....Pages 287-299
Maximizing Monotone Submodular Functions over the Integer Lattice....Pages 300-311
Submodular Unsplittable Flow on Trees....Pages 312-324
Strong Reductions for Extended Formulations....Pages 325-336
Sum-of-Squares Hierarchy Lower Bounds for Symmetric Formulations....Pages 337-349
Approximation-Friendly Discrepancy Rounding....Pages 350-361
Deciding Emptiness of the Gomory-Chvátal Closure is NP-Complete, Even for a Rational Polyhedron Containing No Integer Point....Pages 362-374
On the Quantile Cut Closure of Chance-Constrained Problems....Pages 375-386
Back Matter....Pages 387-397
....Pages 398-409