E-raamat: Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Liege, Belgium, June 1-3, 2016, Proceedings

This book constitutes therefereed proceedings of the 18th International Conference on IntegerProgramming and Combinatorial Optimization, IPCO 2016, held in Ličge, Belgium,in June 2016. The 33 full papers presented were carefully reviewed and selectedfrom 125 submissions. The conference is a forum for researchers andpractitioners working on various aspects of integer programming andcombinatorial optimization. The aim is to present recent developments intheory, computation, and applications in these areas. The scope of IPCO isviewed in a broad sense, to include algorithmic and structural results ininteger programming and combinatorial optimization as well as revealingcomputational studies and novel applications of discrete optimization topractical problems.

OnApproximation Algorithms for Concave Mixed-Integer QuadraticProgramming.- Centerpoints:A link between optimization and convex geometry.- Rescaled coordinate descentmethods for Linear Programming.- Approximating Min-Cost Chain-ConstrainedSpanning Trees: A Reduction from Weighted to Unweighted Problems.- Max-Cutunder Graph Constraints.- Sparsest cut in planar graphs, maximum concurrent owsand their connections with the max-cut problem.- Intersection Cuts for BilevelOptimization.- Exact Algorithms for the Chance-Constrained Vehicle RoutingProblem.- Extended Formulations in Mixed-integer Convex Programming.- k-Trails: Recognition, Complexity, andApproximations.- Better s-t-Tours by Gao Trees.- Popular Edges and DominantMatchings.- Semidefinite and linear programming integrality gaps for schedulingidentical machines.- Stabilizing networkbargaining games by blocking players.- Round Robin Tournaments Generated by theCircle Method have Maximum Carry-Over.- Extreme Functions

with an ArbitraryNumber of Slopes.- Minimal cut-generating functions are nearly extreme.- On theMixed Binary Representability of Ellipsoidal Regions.- Constant FactorApproximation for ATSP with Two Edge Weights.- Improved ApproximationAlgorithms for Hitting 3-Vertex Paths.- Improved Approximations for CubicBipartite and Cubic TSP.- An approximation algorithm for Uniform Capacitated k-Median problemwith 1 + capacityviolation.- Valid Inequalities for Separable Concave Constraints with IndicatorVariables.- A Polyhedral Approach to Online Bipartite Matching.- On SomePolytopes Contained in the 0,1 Hypercube that Have a Small Chvįtal Rank.- RobustMonotone Submodular Function Maximization.- Maximizing Monotone SubmodularFunctions over the Integer Lattice.- Submodular Unsplittable Flow on Trees.- Strongreductions for extended formulations.- Sum-of-squares lower bounds formaximally symmetric formulations.- Sum-of-squares lower bounds for maximallysymmetric formulations.- Dec

iding Emptiness of the Gomory-Chvįtal Closure isNP-Complete, Even for a Rational Polyhedron Containing No Integer Point.- Onthe quantile cut closure of chance-constrained problems.