Integer programming and combinatorial optimization : 23rd international conference, IPCO 2022, Eindhoven, The Netherlands, June 27-29, 2022, proceedings / / edited by Karen Aardal and Laura Sanità

• Pubblicazione: Cham, Switzerland : , : Springer, , [2022]; ©2022
• Descrizione fisica: 1 online resource (469 pages)
• Disciplina: 519.64
• Soggetto topico: Combinatorial optimization
• Persona (resp. second.): AardalK (Karen); SanitàLaura
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Intro -- 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.
• Titolo autorizzato: Integer Programming and Combinatorial Optimization
• ISBN: 3-031-06901-3
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910574063603321
• Lo trovi qui: Univ. Federico II
• Serie: Lecture Notes in Computer Science