Preface
Conference Organization
Contents
Improving the Approximation Ratio for Capacitated Vehicle Routing
1 Introduction
1.1 Formal Problem Description
1.2 Outline
1.3 Related Work
1.4 Review of the Classical Algorithms
2 Difficult Instances
3 Vehicle Routing with Target Groups
4 Clustering Algorithm
5 Weak Fractional Solutions
6 Solving Vehicle Routing with Target Groups
References
Online k-Taxi via Double Coverage and Time-Reverse Primal-Dual
1 Introduction
1.1 Related Work and Known Results
1.2 Our Contribution
2 Preliminaries
3 LP Formulations
3.1 Dual Transformation
4 The k-Taxi Problem on HSTs
4.1 Constructing the Dual Solution
4.2 Finalizing the Analysis for k-Taxi on HSTs
5 The k-Taxi Problem on Weighted Trees
References
Approximating the Discrete Time-Cost Tradeoff Problem with Bounded Depth
1 Introduction
2 Results and Outline
3 The Vertex Cover LP
4 Rounding Fractional Vertex Covers in d-Partite Hypergraphs
5 Inapproximability
6 Reducing Vertex Deletion to Constant Depth
References
Sum-of-Squares Hierarchies for Binary Polynomial Optimization
1 Introduction
1.1 The Sum-of-Squares Hierarchy on the Boolean Cube
1.2 A Second Hierarchy of Bounds
1.3 Asymptotic Analysis for Both Hierarchies
1.4 Related Work
1.5 Overview of the Proof
2 Sketch of Proof
2.1 The Polynomial Kernel Technique
2.2 Fourier Analysis on Bn and the Funk-Hecke Formula
2.3 Optimizing the Choice of the Univariate Polynomial u
2.4 The Inner Lasserre Hierarchy and Orthogonal Polynomials
3 Concluding Remarks
References
Complexity, Exactness, and Rationality in Polynomial Optimization
1 Introduction
2 Existence of Rational Feasible Solutions
3 NP-Hardness of Determining Existence of Rational Feasible Solutions
4 Short Certificate of Feasibility: An Almost Feasible Point
References
On the Geometry of Symmetry Breaking Inequalities
1 Introduction
2 Preliminaries
3 The Geometric Structure of Fundamental Domains
4 Generalized Dirichlet Domains
4.1 The Lex-Max Fundamental Domain
5 Overrepresentation of Orbit Representatives
6 Future Work
References
Affinely Representable Lattices, Stable Matchings, and Choice Functions
1 Introduction
2 The QF-Model
3 Affine Representability of the Stable Matching Lattice
4 Algorithms
5 The Convex Hull of Lattice Elements: Proof of Theorem2
References
A Finite Time Combinatorial Algorithm for Instantaneous Dynamic Equilibrium Flows
1 Introduction
1.1 Our Contribution and Proof Techniques
1.2 Related Work
2 Model and the Extension-Algorithm
3 Finite IDE-Construction Algorithm
4 Computational Complexity of IDE
5 Conclusion
References
A Combinatorial Algorithm for Computing the Degree of the Determinant of a Generic Partitioned Polynomial Matrix with 22 Submatrices
1 Introduction
2 Matchings, Potentials, and Min-Max Formulas
2.1 Matching Concepts
2.2 Minimax Theorems
2.3 Elimination
3 Augmenting Path
3.1 Definition
3.2 Finding an Augmenting Path
4 Augmentation
4.1 Base Case: R= P0 and P0 Is a Path
4.2 General Case
References
On the Implementation and Strengthening of Intersection Cuts for QCQPs
1 Introduction
1.1 Literature Review
2 Maximal Quadratic-Free Sets and Cut Computations
2.1 Case 1: I0 = 0 and = 0
2.2 Case 2: I0 = 0 and > 0
2.3 Case 3: I0 = 0 and < 0
2.4 Case 4: I0 =0
2.5 Implied Quadratics in an Extended Space
3 Strengthening Procedure
4 Computational Experiments
5 Final Remarks
References
Lifting Convex Inequalities for Bipartite Bilinear Programs
1 Introduction
1.1 Generating Strong Cutting Planes Through Lifting
1.2 Goal of This Paper
1.3 Main Contributions
1.4 Notation and Organization of the Paper
2 Main Results
2.1 Sufficient Conditions Under Which Seed Inequalities Can Be Lifted
2.2 A Framework for Sequence-Independent Lifting
2.3 A Seed Inequality from a ``Minimal Covering Set''
2.4 Lifting the Bilinear Cover Inequality (4)
3 Future Directions
References
A Computational Status Update for Exact Rational Mixed Integer Programming
1 Introduction
2 Numerically Exact Mixed Integer Programming
3 Extending and Improving an Exact MIP Framework
4 Computational Study
References
New Exact Techniques Applied to a Class of Network Flow Formulations
1 Introduction
2 Network Flow Formulations
3 Column Generation
4 Variable Fixing Based on Reduced Costs
5 A Variable-Selection Method Based on Arcs
5.1 Advantages of Branching Based on Arc Flow Variables
5.2 Variable-Selection Based on Arcs
5.3 Examples of Arc Families
6 A Solution Method for Network Flow Formulations
7 An Application to the Cutting Stock Problem
8 Computational Experiments
9 Conclusions
References
Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets
1 Introduction
2 A Dominance Relation
3 Multi-cover Inequalities
4 Antichain Multi-cover Inequalities
5 Facet-Inducing MCI
6 Conclusion
References
Semi-streaming Algorithms for Submodular Matroid Intersection
1 Introduction
2 Preliminaries
3 The Local Ratio Technique for Weighted Matroid Intersection
3.1 Local-Ratio Technique for Weighted Matching
3.2 Adaptation to Weighted Matroid Intersection
3.3 Analysis of Algorithm 1
4 Making the Algorithm Memory Efficient
5 More Than Two Matroids
References
Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems
1 Introduction
2 Pfaffian Pairs and Pfaffian Parities
2.1 Preliminaries
2.2 Pfaffian Pairs and Parities
3 Combinatorial Examples
3.1 Perfect Matchings of Pfaffian Graphs
3.2 Shortest Disjoint S-T-U Paths on Undirected Graphs
4 Algorithms
4.1 Counting on Unweighted Pfaffian Pairs and Parities
4.2 Counting on Weighted Pfaffian Parities
References
On the Recognition of {a,b,c}-Modular Matrices
1 Introduction
1.1 Our Results
2 Notation and Preliminaries
3 Proof of Theorem 1
4 Proof of Theorem 2
5 Proof of Theorem 3
References
On the Power of Static Assignment Policies for Robust Facility Location Problems
1 Introduction
1.1 Our Contributions
2 Warm-Up: Uncapacitated Robust Facility Location
2.1 Problem Formulation
2.2 Static Assignment Policy
3 Soft-Capacitated Robust Facility Location
3.1 Problem Formulation
3.2 An O ( logk loglogk )-Approximation Algorithm
4 Conclusion
References
Robust k-Center with Two Types of Radii
1 Introduction
2 Detailed Description of Our Approach
2.1 CGK's Approach and Its Shortcomings
2.2 Our Idea
2.3 Discussion
3 Approximating Well-Separated Robust 2-NUkC
4 The Main Algorithm: Proof of Theorem 1
References
Speed-Robust Scheduling
1 Introduction
2 Speed-Robust Scheduling with Infinitesimal Jobs
2.1 General Speeds
2.2 Speeds in 0,1
3 Speed-Robust Scheduling with Discrete Jobs
4 Speed-Robust Scheduling with Equal-Size Jobs
4.1 General Speeds
4.2 Speeds in 0,1
References
The Double Exponential Runtime is Tight for 2-Stage Stochastic ILPs
1 Introduction
2 Advanced Hardness for Quadratic Congruences
3 Reduction from the Quadratic Congruences Problem
4 Runtime Bounds for 2-Stage Stochastic ILPs Under ETH
References
Fast Quantum Subroutines for the Simplex Method
1 Introduction
2 Comparison with the Existing Literature
3 Overview of the Simplex Method
4 Quantum Implementation: Overview
5 Technical Discussion
References
Maximum Weight Disjoint Paths in Outerplanar Graphs via Single-Tree Cut Approximators
1 Introduction
1.1 A Single-Subtree Cut Sparsifier and Related Results
2 Single Spanning Tree Cut Approximator in Outerplanar Graphs
2.1 Converting Flow-Sparsifiers in Outerplanar Graphs to Distance-Sparsifiers in Trees
2.2 An Algorithm to Build a Distance-Sparsifier of a Tree
3 Maximum Weight Disjoint Paths
3.1 Required Elements
3.2 Proof of the Main Theorem
4 Conclusions
References
A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem
1 Introduction
1.1 Our Contribution
1.2 Comparison to Previous Works
1.3 Other Related Works
1.4 Overview of the Proof
2 Finding 2-good Induced Subgraphs
2.1 Restricting to Chordal, 2P3-free Neighborhoods
2.2 The Twin-Free Case
2.3 Handling True Twins in G[N[v0]]
2.4 Putting Things Together
3 Conclusion
References
Fixed Parameter Approximation Scheme for Min-Max k-Cut
1 Introduction
1.1 Results
1.2 Outline of Techniques
2 Tools for the Fixed-Parameter Algorithm
3 Fixed-Parameter Algorithm Parameterized by k and Solution Size
4 Conclusion
References
Computational Aspects of Relaxation Complexity
1 Introduction
2 Computable Bounds on the Relaxation Complexity
3 Computational Complexity in Dimension 2
4 Discrete Rectangular Boxes
5 Numerical Experiments
References
Complexity of Branch-and-Bound and Cutting Planes in Mixed-Integer Optimization - II
1 Introduction
1.1 Framework for Mathematical Analysis
1.2 Our Results
2 Proofs
2.1 Proof of Theorem 1
2.2 Proof of Theorem 2
2.3 Proofs of Theorems 5 And 6
References
Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs
1 Introduction
2 Computing the Dimension of a Face
3 Measuring the Strength of a Single Inequality
4 Computational Study
A Additional Plots
References
Proximity Bounds for Random Integer Programs
1 Introduction
2 Main Result and Notation
2.1 Notation
2.2 Definition of dist(A)
2.3 Definition of dist()
2.4 An Asymptotic Version of dist()
2.5 Main Result
3 A Theorem of Schmidt
4 Typical Cramer's Rule Ratios
4.1 The Real Grassmannian
4.2 Probability Spaces
4.3 Cramer's Rule Ratios
5 Proof of Main Result
References
On the Integrality Gap of Binary Integer Programs with Gaussian Data
1 Introduction
1.1 Techniques
1.2 Relation to Branch and Bound
1.3 Related Work
1.4 Organization
2 Preliminaries
2.1 Basic Notation
2.2 The Dual Program, Gap Formula and the Optimal Solutions
2.3 Gaussian and Sub-Gaussian Random Variables
2.4 A Local Limit Theorem
2.5 Rounding to Binary Solutions
3 Properties of the Optimal Solutions
4 Properties of the 0 Columns
5 Proof of Theorem1
References
Linear Regression with Mismatched Data: A Provably Optimal Local Search Algorithm
1 Introduction
2 A Local Search Method
3 Theoretical Guarantees for Local Search
3.1 A Restricted Eigenvalue (RE) Condition
3.2 One-Step Decrease
3.3 Main Results
4 Experiments
5 Appendix: Proofs and Technical Results
5.1 Proof of Lemma1
5.2 Proof of Lemma2
5.3 Proof of Claim (3.14) in Theorem1
References
A New Integer Programming Formulation of the Graphical Traveling Salesman Problem
1 Introduction
2 Basic Formulations
2.1 Symmetric TSP
2.2 Symmetric GTSP
3 New Constraints
3.1 Enforcing Even Degree Without Disjunctions
3.2 Spanning Tree Constraints
4 A New Mixed IP Formulation
4.1 Proving the Formulation
4.2 Addressing the Naddef Challenge
5 Relaxations and Steiner Nodes
5.1 Symmetric GTSP with Steiner Nodes
5.2 Preventing the Half-z Path Without Spanning Trees
5.3 Removing Steiner Nodes
6 Computational Results
References
Implications, Conflicts, and Reductions for Steiner Trees
1 Introduction
1.1 Contribution
1.2 Preliminaries and Notation
2 From Implications to Reductions
2.1 The Bottleneck Steiner Distance
2.2 A Stronger Bottleneck Concept
2.3 Bottleneck Steiner Reductions Beyond Edge Deletion
3 From Reductions to Conflicts
3.1 Node Replacement
3.2 Edge Replacement
4 From Steiner Distances and Conflicts to Extended Reduction Techniques
4.1 The Framework
4.2 Reduction Criteria
5 Exact Solution
5.1 Branch-and-cut
5.2 Computational Results
6 Outlook
References
Author Index