Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Combinatorial optimization : 7th International Symposium, ISCO 2022, virtual event, May 18-20, 2022, revised selected papers / / Ivana Ljubic [and three others] editors
| Combinatorial optimization : 7th International Symposium, ISCO 2022, virtual event, May 18-20, 2022, revised selected papers / / Ivana Ljubic [and three others] editors |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2022] |
| Descrizione fisica | 1 online resource (340 pages) |
| Disciplina | 519.64 |
| Collana | Lecture notes in computer science |
| Soggetto topico | Combinatorial optimization |
| ISBN | 3-031-18530-7 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| 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. |
| Record Nr. | UNINA-9910631085503321 |
| Cham, Switzerland : , : Springer, , [2022] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Combinatorial optimization : 7th International Symposium, ISCO 2022, virtual event, May 18-20, 2022, revised selected papers / / Ivana Ljubic [and three others] editors
| Combinatorial optimization : 7th International Symposium, ISCO 2022, virtual event, May 18-20, 2022, revised selected papers / / Ivana Ljubic [and three others] editors |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2022] |
| Descrizione fisica | 1 online resource (340 pages) |
| Disciplina | 519.64 |
| Collana | Lecture notes in computer science |
| Soggetto topico | Combinatorial optimization |
| ISBN | 3-031-18530-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| 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. |
| Record Nr. | UNISA-996500062603316 |
| Cham, Switzerland : , : Springer, , [2022] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Operations Research Proceedings 2015 [[electronic resource] ] : Selected Papers of the International Conference of the German, Austrian and Swiss Operations Research Societies (GOR, ÖGOR, SVOR/ASRO), University of Vienna, Austria, September 1-4, 2015 / / edited by Karl Franz Dörner, Ivana Ljubic, Georg Pflug, Gernot Tragler
| Operations Research Proceedings 2015 [[electronic resource] ] : Selected Papers of the International Conference of the German, Austrian and Swiss Operations Research Societies (GOR, ÖGOR, SVOR/ASRO), University of Vienna, Austria, September 1-4, 2015 / / edited by Karl Franz Dörner, Ivana Ljubic, Georg Pflug, Gernot Tragler |
| Edizione | [1st ed. 2017.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 |
| Descrizione fisica | 1 online resource (XV, 721 p. 171 illus.) |
| Disciplina | 658.4034 |
| Collana | Operations Research Proceedings, GOR (Gesellschaft für Operations Research e.V.) |
| Soggetto topico |
Operations research
Decision making Management science Production management Game theory Engineering economics Engineering economy Operations Research/Decision Theory Operations Research, Management Science Operations Management Game Theory, Economics, Social and Behav. Sciences Engineering Economics, Organization, Logistics, Marketing |
| ISBN | 3-319-42902-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Part I: Award Winners -- Part II: Discrete Optimization, Integer Programming, Graphs and Networks -- Part III: Logistics and Transportation -- Part IV: Metaheuristics and Multiple Criteria Decision Making -- Part V: OR for Security, Policy Modeling and Public Sector OR -- Part VI: Production, Operations Management, Supply Chains, Stochastic Models and Simulation -- Part VII: Analytics and Forecasting -- Part VIII: Financial Modeling, Accounting and Game Theory -- Part IX: Continuous and Stochastic Optimization, Control Theory -- Part X: Scheduling, Project Management and Health Services -- Part XI: Energy. . |
| Record Nr. | UNINA-9910254916803321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||