Full Description
This book constitutes the
refereed proceedings of the 18th International Conference on Integer
Programming and Combinatorial Optimization, IPCO 2016, held in Liège, Belgium,
in June 2016. The 33 full papers presented were carefully reviewed and selected
from 125 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.
Contents
On
Approximation Algorithms for Concave Mixed-Integer QuadraticProgramming.- Centerpoints:
A link between optimization and convex geometry.- Rescaled coordinate descent
methods for Linear Programming.- Approximating Min-Cost Chain-Constrained
Spanning Trees: A Reduction from Weighted to Unweighted Problems.- Max-Cut
under Graph Constraints.- Sparsest cut in planar graphs, maximum concurrent ows
and their connections with the max-cut problem.- Intersection Cuts for Bilevel
Optimization.- Exact Algorithms for the Chance-Constrained Vehicle Routing
Problem.- Extended Formulations in Mixed-integer Convex Programming.- k-Trails: Recognition, Complexity, and
Approximations.- Better s-t-Tours by Gao Trees.- Popular Edges and Dominant
Matchings.- Semidefinite and linear programming integrality gaps for scheduling
identical machines.- Stabilizing network
bargaining games by blocking players.- Round Robin Tournaments Generated by the
Circle Method have Maximum Carry-Over.- Extreme Functions with an Arbitrary
Number of Slopes.- Minimal cut-generating functions are nearly extreme.- On the
Mixed Binary Representability of Ellipsoidal Regions.- Constant Factor
Approximation for ATSP with Two Edge Weights.- Improved Approximation
Algorithms for Hitting 3-Vertex Paths.- Improved Approximations for Cubic
Bipartite and Cubic TSP.- An approximation algorithm for Uniform Capacitated k-Median problem
with 1 + ϵ capacity
violation.- Valid Inequalities for Separable Concave Constraints with Indicator
Variables.- A Polyhedral Approach to Online Bipartite Matching.- On Some
Polytopes Contained in the 0,1 Hypercube that Have a Small Chvátal Rank.- Robust
Monotone Submodular Function Maximization.- Maximizing Monotone Submodular
Functions over the Integer Lattice.- Submodular Unsplittable Flow on Trees.- Strong
reductions for extended formulations.- Sum-of-squares lower bounds for
maximally symmetric formulations.- Sum-of-squares lower bounds for maximally
symmetric formulations.- Deciding Emptiness of the Gomory-Chvátal Closure is
NP-Complete, Even for a Rational Polyhedron Containing No Integer Point.- On
the quantile cut closure of chance-constrained problems.
