Preface
Organization
Contents
Total Dual Dyadicness and Dyadic Generating Sets
1 Introduction
1.1 Totally Dual p-adic Systems and p-adic Generating Sets
1.2 Connection to Integral Polyhedra and TDI Systems
1.3 Examples
2 Density Lemma and the Theorem of the Alternative
3 p-Adic Generating Sets for Subspaces and Cones
4 Totally Dual p-adic Systems
5 p-Adic Polyhedra
6 T-joins and Perfect Matchings
References
Faster Goal-Oriented Shortest Path Search for Bulk and Incremental Detailed Routing
1 Introduction
1.1 Problem Statement
1.2 Previous Work and Our Results
2 Distances Without Preprocessing in the Simple Model
3 Logarithmic Query Time in the Simple Model
4 The General Model
5 Practical Aspects
5.1 Implementation
5.2 Reservations and Discounts for Incremental Routing
References
On the Maximal Number of Columns of a -modular Matrix
1 Introduction
2 Counting by Residue Classes
2.1 Small Dimensions and Lower Bounds in the Shifted Setting
3 A Polynomial Upper Bound on h_s(m)
4 Feasibility of Sauer Matrices in Low Dimensions
5 Discussion and Open Problems
References
The Simultaneous Semi-random Model for TSP
1 Introduction
1.1 Our Contributions
1.2 Technical Overview
1.3 Additional Related Work
2 Preliminaries
3 An Improved Approximation for Local Search in the Simultaneous Semi-random Model
3.1 An Improved Worst-Case Approximation for Local Search
3.2 Proof of Theorem 1
4 Improved Approximations Require poly(n) Random Points
4.1 A Framework for Simultaneous Semi-random Lower Bounds
4.2 The Construction
References
A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem
1 Introduction
1.1 Our Results
1.2 Our Techniques
2 The Analysis of the LP-Based Algorithm
2.1 Preliminaries
2.2 The Analysis of the Algorithm
3 Conclusion
A Deferred Proofs
References
Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition
1 Introduction
1.1 Our Results
1.2 Technical Overview
1.3 Preliminaries
2 Structural Theorem
2.1 No Moderate-Sized Min-Cuts
2.2 Trim and Shave Operations
2.3 Proof of Theorem 2
References
Improving the Cook et al. Proximity Bound Given Integral Valued Constraints
1 Introduction
1.1 Preliminaries and Notation
1.2 Dimension Reduction
2 Proximity for 1, 2, and 3-Dimensional Polyhedra
3 Lifting Proximity Results to Higher Dimensions
4 Proof of the Main Theorem
5 Proximity in the Strictly -Modular Case
6 A Lower Bound Example
References
Sparse Multi-term Disjunctive Cuts for the Epigraph of a Function of Binary Variables
1 Introduction
2 Sparse Multi-term 0-1 Disjunctive Cuts
2.1 Generating Multi-term 0-1 Disjunctive Cuts
2.2 I-Sparse Inequalities
2.3 Accelerating the Evaluation of IR()
3 Two Selection Rules for the Support I
3.1 A Greedy Rule Based on a Monotone Submodular Approximation
3.2 A Cutting-Plane Approximation Rule
4 Computational Results
5 Future Directions
References
A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time
1 Introduction
1.1 Related Work
2 Preliminaries: Tree Decompositions
3 The LP Relaxation and the Rounding Algorithm
3.1 The LP Relaxation
3.2 The Rounding Algorithm
References
Optimal Item Pricing in Online Combinatorial Auctions
1 Introduction
1.1 Context and Related Work
1.2 A Technical Highlight and Additional Results
2 Model
3 Random Valuations
4 Single-Minded Valuations
4.1 Matching in Graphs: d=2
4.2 Hypergraph Matching: d>2
References
On Circuit Diameter Bounds via Circuit Imbalances
1 Introduction
1.1 Our Contributions
2 Preliminaries
3 The Circuit Diameter Bound
4 Diameter Bounds for the Capacitated Case
5 A Circuit-Augmentation Algorithm for Feasibility
6 A Circuit-Augmentation Algorithm for Optimization
References
A Simple Method for Convex Optimization in the Oracle Model
1 Introduction
2 Algorithm
3 Computational Experiments
References
On the Complexity of Separation from the Knapsack Polytope
1 Introduction
2 Extended Cover Inequality Separation
3 (1,k)-Configuration Inequality Separation
4 Weight Inequality Separation
References
Simple Odd -Cycle Inequalities for Binary Polynomial Optimization
1 Introduction
2 Building Block Inequalities
3 Simple Odd -Cycle Inequalities
4 Separation Algorithm
5 Relation to Non-simple Odd -Cycle Inequalities
References
Combinatorial Algorithms for Rooted Prize-Collecting Walks and Applications to Orienteering and Minimum-Latency Problems
1 Introduction
2 LP-Relaxation for the Prize-Collecting-Walks Problem
3 A Combinatorial Algorithm
4 Applications for Orienteering Problems
5 Applications for the k Minimum-Latency Problem
6 Computational Results for Orienteering
References
Intersecting and Dense Restrictions of Clutters in Polynomial Time
1 Introduction
2 The Unifying Theorem
3 k-Wise Intersecting Clutters
4 Dense Clutters
5 Finding Delta or Blocker of Extended Odd Hole Minors
References
LP-Based Approximations for Disjoint Bilinear and Two-Stage Adjustable Robust Optimization
1 Introduction
1.1 Our Contributions
2 A Polylogarithmic Approximation for PDB
3 From Disjoint Bilinear Optimization to Two-Stage Adjustable Robust Optimization
4 Numerical Experiments
5 Conclusion
References
A Constant-Factor Approximation for Generalized Malleable Scheduling Under M-Concave Processing Speeds
1 Introduction
1.1 Generalized Malleable Scheduling and Main Results
1.2 Submodularity, M-Concavity, and Matroids
1.3 Organization of the Paper
2 The Configuration LP
3 Overview of the Algorithm
4 Description and Analysis of the Intermediate Steps
4.1 Step 1: Single-machine Assignments for J1
4.2 Step 2: Assignments with Low Total Speed for J2
4.3 Step 3A: Splitting Assignments with High Total Speed
4.4 Step 3B: Constructing an Integer Assignment for J3
5 Generalized Malleable Jobs and Fair Allocations
6 Conclusion
References
Improved Approximations for Capacitated Vehicle Routing with Unsplittable Client Demands
1 Introduction
1.1 Related Work
2 Preliminaries
3 A Combinatorial 3.25-Approximation
3.1 Analysis
4 An Improved LP-Based Approximation
4.1 Analysis
References
SOCP-Based Disjunctive Cuts for a Class of Integer Nonlinear Bilevel Programs
1 Introduction
2 Disjunctive Cut Methodology
2.1 Preliminaries
2.2 Deriving Disjunctive Cuts
2.3 Separation Procedure for Disjunctive Cuts
3 Solution Methods Using Disjunctive Cuts
3.1 A Branch-and-Cut Algorithm
3.2 An Integer Cutting Plane Algorithm
4 Computational Analysis
4.1 Instances
4.2 Computational Environment
4.3 Numerical Results
5 Conclusions
References
Non-adaptive Stochastic Score Classification and Explainable Halfspace Evaluation
1 Introduction
1.1 Results and Techniques
1.2 Related Work
2 Preliminaries
3 The Stochastic Score Classification Algorithm
3.1 The Algorithm
3.2 The Analysis
3.3 Proof of Lemma 3
4 Computational Results
References
On the Complexity of Finding Shortest Variable Disjunction Branch-and-Bound Proofs
1 Introduction
2 Preliminaries
2.1 Binary Programs and Branch-and-Bound Proofs
2.2 Boolean Formulas and the Exponential Time Hypothesis
3 Hardness of Approximation
4 (Non-)Automatizability of Branch-and-Bound
5 #P-Hardness of Exact Computation
6 Outlook
References
Matroid-Based TSP Rounding for Half-Integral Solutions
1 Introduction
2 Notation and Preliminaries
3 Samplers
3.1 Samplers for Even |V(H)|
3.2 Correlation Properties of Samplers
4 Sampling Algorithm for General Solutions
4.1 The Cut Hierarchy
5 Analysis Part I: The Even-at-Last Property
6 Analysis Part II: The O-Join and Charging
References
The Two-Stripe Symmetric Circulant TSP is in P
1 Introduction
2 Background and Notation
2.1 Circulant Graphs
2.2 Cylinder Graphs
2.3 Trivial Cases
2.4 Main Result
2.5 Previous Results on Two-Stripe TSP
3 GG Paths and a Reduction to Hamiltonian Paths on Cylinder Graphs
3.1 Reduction of 2-Stripe Problem to Cylinder Graph Problem
3.2 GG Paths
4 Proof of Main Result
5 The Algorithm
6 Proof Sketch of Theorem 3
7 Conclusion
References
An Abstract Model for Branch-and-Cut
1 Introduction
2 Preliminaries
3 The Abstract Branch-and-Cut Model
4 Optimizing Tree Size
5 Optimizing Tree Time
5.1 Time-Functions Bounded by a Polynomial
5.2 Adding k Cuts Along Every Root-to-Leaf Path
5.3 Proof of Theorem 13
6 Conclusion and Potential Extensions
References
Neural Networks with Linear Threshold Activations: Structure and Algorithms
1 Introduction
2 Representability Results
3 Proof of Proposition 1
4 Globally Optimal Empirical Risk Minimization
4.1 Preliminaries
4.2 Proof of Theorem 2
5 Open Questions
References
A PTAS for the Horizontal Rectangle Stabbing Problem
1 Introduction
1.1 Our Results
1.2 Further Related Work
2 Dynamic Program
2.1 Preprocessing Step
2.2 Description of the Dynamic Program
2.3 Definition of DP-Decision Tree
2.4 Analysis of DP-Decision Tree
3 -Large Rectangles
4 Conclusion
References
Lattice-Free Simplices with Lattice Width 2d - o(d)
1 Introduction
2 Lattice-Free Simplices of Large Lattice Width
3 An Infinite-Dimensional View
4 Local Maximizers in Dimensions 4 and 5
5 Open Questions
References
Graph Coloring and Semidefinite Rank
1 Introduction
2 Preliminaries
3 The Strict Vector Chromatic Number SDP
4 A Semidefinite Program with Costs
5 Experimental Results
6 Open Questions
References
A Competitive Algorithm for Throughput Maximization on Identical Machines
1 Introduction
1.1 Our Results
1.2 Scheduling Policies
1.3 Algorithms and Technical Overview
1.4 Related Work
2 Structure of Optimal Schedule
3 SRPT is Competitive with Non-viable Jobs
4 SRPT and MLax Are Competitive with Viable Jobs
4.1 Proof of Lemma 9
4.2 Proof of Lemma 10
5 Putting it all Together
References
The Limits of Local Search for Weighted k-Set Packing
1 Introduction
1.1 The Unit Weight Case
1.2 General Weights and the MWIS in d-Claw Free Graphs
1.3 Berman's Algorithm SquareImp
2 Our Contribution
3 Preliminaries
4 Our Algorithm LogImp
4.1 Classification of Vertices from A*
4.2 Missing, Profitable and Helpful Vertices
4.3 Local Improvements of Logarithmic Size
4.4 A Polynomial Running Time
5 The Lower Bound
6 Conclusion
References
The Secretary Problem with Distributions
1 Introduction
1.1 Our Contributions
1.2 Related Literature
1.3 Organization
2 The Secretary Problem with Distributions
3 Extension to Negative Dependence
4 Limited Knowledge: Samples from Distributions
References
Approximate [] in Time 20.802 n - Now in Any Norm!
1 Introduction
2 Approximate [] in 20.802 n Time
2.1 Covering K with Few Ellipsoids and Vice Versa
2.2 Approximate [K] Using an Oracle for Approximate [2]
3 Approximate [] in Time 20.802 n
References
Author Index