The Holy Bible containing the Old Testament and the New newly translated out of the original tongues and with the former translations diligently compared and revised by his Majesties speciall command. Appointed to be read in churches

• Record Nr.: UNISA996397236203316
• Pubbl/distr/stampa: Printed by Iohn Field printer to the Uneversete sic of Cambrig; England
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia

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à

• Record Nr.: UNISA996475770403316
• Pubbl/distr/stampa: Cham, Switzerland : , : Springer, , [2022]; ©2022
• ISBN: 3-031-06901-3
• Descrizione fisica: 1 online resource (469 pages)
• Collana: Lecture Notes in Computer Science ; ; v.13265
• Disciplina: 519.64
• Soggetti: Combinatorial optimization
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• 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&gt -- 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.