Combinatorial optimization : 7th International Symposium, ISCO 2022, virtual event, May 18-20, 2022, revised selected papers / / Ivana Ljubic [and three others] editors

• Pubblicazione: Cham, Switzerland : , : Springer, , [2022]; ©2022
• Descrizione fisica: 1 online resource (340 pages)
• Disciplina: 519.64
• Soggetto topico: Combinatorial optimization
• Persona (resp. second.): LjubicIvana
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Intro -- Preface -- Organization -- Plenary Lectures -- Graphical Designs -- Advances in Approximation Algorithms for Tree Augmentation -- Algorithmic Data Science -- Recent Algorithmic Advances for Maximum-Entropy Sampling -- Contents -- Polyhedra and Algorithms -- New Classes of Facets for Complementarity Knapsack Problems -- 1 Introduction -- 2 Notations, Assumptions, and Previous Work -- 3 Separation Complexity of Lifted Cover Inequalities for CKP -- 4 New Families of Facet-Defining Inequalities -- 5 Future Direction -- References -- Branch-and-Cut for a 2-Commodity Flow Relocation Model with Time Constraints -- 1 Introduction -- 2 A TEN Model for the Item Relocation Problem -- 3 The Projected IRP Model -- 3.1 Extended Subtour Constraints and Projected Cost -- 3.2 Separating the Extended Subtour Constraints -- 4 Algorithmic Handling and Numerical Experiments -- 4.1 Separation Algorithm -- 4.2 Numerical Experiments -- 5 Conclusion: A Brief Discussion of the Lift Issue -- References -- The Constrained-Routing and Spectrum Assignment Problem: Valid Inequalities and Branch-and-Cut Algorithm -- 1 Introduction -- 2 The Constrained-Routing and Spectrum Assignment Problem -- 3 Integer Linear Programming Formulation -- 4 Valid Inequalities and Facets -- 4.1 Edge-Capacity-Cover Inequalities -- 4.2 Edge-Interval-Capacity-Cover Inequalities -- 4.3 Edge-Interval-Clique Inequalities -- 4.4 Edge-Slot-Assignment-Clique Inequalities -- 4.5 Slot-Assignment-Clique Inequalities -- 5 Branch-and-Cut Algorithm -- 6 Computational Study -- 7 Conclusion -- References -- Polyhedra and Combinatorics -- Top-k List Aggregation: Mathematical Formulations and Polyhedral Comparisons -- 1 Introduction -- 2 Preliminaries -- 3 Integer Programming Formulations -- 4 Polyhedral Comparison -- 5 Concluding Remarks -- References -- Bounded Variation in Binary Sequences. ; 1 Introduction -- 2 Penalized Variation -- 3 Bounded Variation -- 4 Conclusion and Future Work -- References -- On Minimally Non-firm Binary Matrices -- 1 Introduction -- 2 Preliminaries -- 3 Simplicial 1s and Stretching -- 4 Superfirm Matrices and Odd Holes -- 5 Four Infinite Classes of Minimally Non-firm Matrices -- 6 Conclusion -- References -- Few Induced Disjoint Paths for H-Free Graphs -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Results -- 2 Polynomial-Time Algorithms -- 3 Completing the Proof of Theorem 2 -- 3.1 Omitting ``H''-Graphs and Six-Vertex Cycles -- 4 Conclusions -- References -- On Permuting Some Coordinates of Polytopes -- 1 Introduction and Motivation -- 2 (More) Background and Related Work -- 2.1 Relevant Polytopes -- 3 Results -- 3.1 Parity Constraints via Partial Permutations -- 3.2 Partial Permutation over Quad-Valued Coordinates -- 3.3 Partial Permutation over Three-Valued Coordinates -- 3.4 Sorting Polytopes -- 4 Concluding Remarks -- References -- Non-linear Optimization -- Piecewise Linearization of Bivariate Nonlinear Functions: Minimizing the Number of Pieces Under a Bounded Approximation Error -- 1 Problem Description and State of the Art -- 2 Definitions -- 3 A Framework for Solving the R2-Corridor Fitting Problem -- 3.1 Key Idea 1: Management of the Corridor Domain -- 3.2 Key Idea 2: The Maximal Piece in Direction d Problem -- 3.3 Key Idea 3: Computing a Feasible Solution of a Maximal Piece in Direction d Problem -- 4 Framework Key Points Instantiation -- 4.1 Scoring the Quality of Pieces -- 4.2 Choose a Progress Direction -- 4.3 Inner Approximation of a Corridor -- 5 Numerical Experiments -- 6 Conclusion -- References -- An Outer-Approximation Algorithm for Maximum-Entropy Sampling -- 1 Introduction -- 2 Outer Approximation -- 3 Convex Relaxations for [MESP]MESP -- 4 Disjunctive Cuts -- 5 Experiments. ; 6 Next Steps -- References -- Mitigating Anomalies in Parallel Branch-and-Bound Based Algorithms for Mixed-Integer Nonlinear Optimization -- 1 Introduction -- 2 Anomalies in Parallel Algorithms -- 3 Opportunistic Parallel Branch-and-Bound in Minotaur -- 4 Reducing Detrimental Anomalies in Parallel NLP-BB -- 4.1 Unambiguous Branching Functions -- 4.2 Unambiguous Reliability Branching Scheme -- 4.3 A Hybrid Unambiguous Node Selection Strategy -- 4.4 Nondetrimental NLP-BB -- 5 Reducing Detrimental Anomalies in Parallel QG -- 6 Computational Results -- 7 Conclusions and Future Directions -- References -- Game Theory -- Exact Price of Anarchy for Weighted Congestion Games with Two Players -- 1 Introduction -- 2 Results -- 3 LP Based Proofs -- 4 Concluding Remarks -- References -- Nash Balanced Assignment Problem -- 1 Introduction -- 2 LP Formulation for BAP -- 3 Nash Fairness Solutions for the AP -- 3.1 Proportional Fairness -- 3.2 Characterization of NF Solutions for the AP -- 3.3 Existence of NF Solutions -- 4 Finding All NF Solutions for the AP -- 4.1 Upper Bound for the Number of NF Solutions -- 4.2 Algorithm for Finding All NF Solutions -- 4.3 Numerical Results -- 5 Conclusion -- References -- Graphs and Trees -- On the Thinness of Trees -- 1 Introduction -- 2 Definitions and Preliminaries -- 3 Characterization and Algorithm -- 3.1 The Algorithm: Rooted Trees, k-critical Vertices and Labels -- 3.2 Computing Thinness of Trees and Finding a Consistent Solution -- References -- Generating Spanning-Tree Sequences of a Fan Graph in Lexicographic Order and Ranking/Unranking Algorithms -- 1 Introduction -- 2 Preliminary -- 3 Generating Fan-Tree Sequences -- 4 Ranking and Unranking Algorithms -- 5 Concluding Remarks -- References -- Cutting and Packing -- High Multiplicity Strip Packing with Three Rectangle Types -- 1 Introduction. ; 2 Solving 2DFSPP in Polynomial Time -- 3 Algorithm for 2DHMSPP with Three Rectangle Types -- 3.1 Partitioning the Packing -- 3.2 Grouping Vertical Sections -- 3.3 Ordering the Configurations -- 3.4 Rounding Fractional Rectangles -- 3.5 None of SCase1, SCase2, and SCase3 are Empty, count = 1, and f1(i) + f2(i) 1 for all Vertical Sections si SCase2 -- 3.6 None of SCase1, SCase2, and SCase3 are Empty, count = 1, and f1(i) + f2(i) > -- 1 for at Least One Vertical Section si SCase2 -- 4 Polynomial Time Implementation -- 5 Conclusion -- References -- Improved Bounds for Stochastic Extensible Bin Packing Under Distributional Assumptions -- 1 Introduction -- 2 Stochastic Extensible Bin Packing -- 3 Second-Order Stochastic Dominance -- 4 Restriction to a Family of Processing Time Distributions -- References -- Applications -- One Transfer per Patient Suffices: Structural Insights About Patient-to-Room Assignment -- 1 Introduction -- 2 Every Patient Has to Be Transferred at Most Once -- 3 No Need to Transfer Patients Arriving in the First Period -- 4 Upper Bounds on the Number of Patient Transfers -- 5 Conclusion -- References -- Tool Switching Problems in the Context of Overlay Printing with Multiple Colours -- 1 Introduction -- 2 CUF-ToSP -- 2.1 Two-Index Formulation for CUF-ToSP -- 3 GOF-ToSP -- 3.1 Five-Index Arc Flow Formulation for GOF-ToSP -- 3.2 Preprocessing -- 4 GOV-ToSP -- 4.1 Six-Index Arc Flow Formulation for GOV-ToSP -- 5 Computational Results -- 5.1 Test Instances -- 5.2 Results -- 6 Conclusions and Future Research -- References -- Optimal Vaccination Strategies for Multiple Dose Vaccinations -- 1 Introduction -- 2 Problem Description and Formulation -- 3 The Matching Approach -- 3.1 Without Capacities -- 3.2 Include Upper Bound on Vaccination Speed and Storage Capacity -- 3.3 Include Multiple Vaccines and Cross-Immunization. ; 4 The Three-Dose Problem -- 5 Conclusion -- References -- Approximation Algorithms -- Pervasive Domination -- 1 Introduction -- 1.1 Our Model -- 1.2 Our Results -- 2 Related Work -- 3 Pervasive Partial Domination -- 3.1 Algorithm Analysis -- 4 Conclusion -- References -- Unified Greedy Approximability Beyond Submodular Maximization -- 1 Introduction -- 2 Weak Submodularity Ratio, -Augmentability, and Independence Systems -- 2.1 Separating Function Classes -- 3 -Augmentability -- 3.1 A Critical Function -- 3.2 -Augmentability on Independence Systems -- 4 Outlook -- References -- Neighborhood Persistency of the Linear Optimization Relaxation of Integer Linear Optimization -- 1 Introduction -- 2 Preliminaries -- 3 Main Results -- 4 Maximality of UTVPI Systems -- 5 Fixed-Parameter Tractability and Two-Approximability for Special Cases -- 6 Conclusion -- References -- Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines -- 1 Introduction and Results -- 1.1 Problem Definition -- 1.2 Our Results -- 1.3 Related Work -- 2 Proofs of Lemmas1 and 2 -- 2.1 Proof of Lemma1 -- 2.2 Proof of Lemma2 -- 3 Proofs of Corollaries1 and 2 -- 3.1 Case of {MST, SP}. -- References -- Author Index.
• Titolo autorizzato: Combinatorial optimization
• ISBN: 3-031-18530-7
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910631085503321
• Lo trovi qui: Univ. Federico II
• Serie: Lecture notes in computer science ; ; 13526.