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

Softcover

ISBN 10: 331933462X ISBN 13: 9783319334622

Publisher: Springer, 2016

Synopsis

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. 

Edition details

• Publisher: Springer
• Publication date: 2016
• ISBN 10: 331933462X
• ISBN 13: 9783319334622
• Binding: Paperback
• Language: English
• Number of pages: 428
• Editor: Louveaux Quentin, Skutella Martin