Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings

Front Matter....Pages I-XI
The Two-Point Fano and Ideal Binary Clutters....Pages 1-12
On Scheduling Coflows....Pages 13-24
Integrality Gaps of Integer Knapsack Problems....Pages 25-38
An Improved Integrality Gap for the Călinescu-Karloff-Rabani Relaxation for Multiway Cut....Pages 39-50
Approximation of Corner Polyhedra with Families of Intersection Cuts....Pages 51-62
The Structure of the Infinite Models in Integer Programming....Pages 63-74
Mixed-Integer Linear Representability, Disjunctions, and Variable Elimination....Pages 75-85
Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time....Pages 86-98
Cutting Planes from Wide Split Disjunctions....Pages 99-110
The Saleman’s Improved Tours for Fundamental Classes....Pages 111-122
The Heterogeneous Capacitated k-Center Problem....Pages 123-135
Local Guarantees in Graph Cuts and Clustering....Pages 136-147
Verifying Integer Programming Results....Pages 148-160
Long Term Behavior of Dynamic Equilibria in Fluid Queuing Networks....Pages 161-172
A 4/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem....Pages 173-185
Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems....Pages 186-198
Compact, Provably-Good LPs for Orienteering and Regret-Bounded Vehicle Routing....Pages 199-211
Discrete Newton’s Algorithm for Parametric Submodular Function Minimization....Pages 212-227
Stochastic Online Scheduling on Unrelated Machines....Pages 228-240
Online Matroid Intersection: Beating Half for Random Arrival....Pages 241-253
Number Balancing is as Hard as Minkowski’s Theorem and Shortest Vector....Pages 254-266
An Improved Deterministic Rescaling for Linear Programming Algorithms....Pages 267-278
Min-Max Theorems for Packing and Covering Odd (u, v)-trails....Pages 279-291
A Quasi-Polynomial Approximation for the Restricted Assignment Problem....Pages 292-304
Adaptive Submodular Ranking....Pages 305-316
On the Notions of Facets, Weak Facets, and Extreme Functions of the Gomory–Johnson Infinite Group Problem....Pages 317-329
Minimum Birkhoff-von Neumann Decomposition....Pages 330-342
Maximum Matching in the Online Batch-Arrival Model....Pages 343-354
Budget Feasible Mechanisms on Matroids....Pages 355-367
Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method....Pages 368-379
Mixed-Integer Convex Representability....Pages 380-391
High Degree Sum of Squares Proofs, Bienstock-Zuckerberg Hierarchy and CG Cuts....Pages 392-404
Enumeration of Integer Points in Projections of Unbounded Polyhedra....Pages 405-416
Excluded t-Factors in Bipartite Graphs: A Unified Framework for Nonbipartite Matchings and Restricted 2-Matchings....Pages 417-429
Equilibrium Computation in Atomic Splittable Singleton Congestion Games....Pages 430-441
Back Matter....Pages 442-454
....Pages 455-456