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.
Integer Programming and Combinatorial Optimization [[electronic resource] ] : 24th International Conference, IPCO 2023, Madison, WI, USA, June 21–23, 2023, Proceedings / / edited by Alberto Del Pia, Volker Kaibel
| Integer Programming and Combinatorial Optimization [[electronic resource] ] : 24th International Conference, IPCO 2023, Madison, WI, USA, June 21–23, 2023, Proceedings / / edited by Alberto Del Pia, Volker Kaibel |
| Autore | Del Pia Alberto |
| Edizione | [1st ed. 2023.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2023 |
| Descrizione fisica | 1 online resource (494 pages) |
| Disciplina | 519.77 |
| Altri autori (Persone) | KaibelVolker |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Computer science—Mathematics
Mathematics—Data processing Discrete mathematics Application software Mathematics of Computing Computational Mathematics and Numerical Analysis Discrete Mathematics in Computer Science Computer and Information Systems Applications |
| Soggetto non controllato |
Technology
Technology & Engineering |
| ISBN |
9783031327261
9783031327254 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Contents -- Information Complexity of Mixed-Integer Convex Optimization -- 1 First-order Information Complexity -- 1.1 Our Results -- 1.2 Formal Definitions and Statement of Results -- 1.3 Discussion and Future Avenues -- 2 Proof Sketches -- 2.1 Proof Sketch of Theorem 1 -- 2.2 Proof of Theorem 3 -- 2.3 Proof Sketch of Theorem 5 -- 2.4 Proof Sketch of Theorems 2 and 4 -- References -- Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products -- 1 Introduction -- 2 RLT for Bilinear Products -- 3 Detection of Implicit Products -- 4 Separation Algorithm -- 4.1 Row Marking -- 4.2 Projection Filtering -- 5 Computational Results -- 5.1 Setup -- 5.2 Impact of RLT Cuts -- 5.3 Separation -- 5.4 Experiments with Gurobi -- 5.5 Summary -- References -- A Nearly Optimal Randomized Algorithm for Explorable Heap Selection -- 1 Introduction -- 2 The Explorable Heap Selection Problem -- 3 A New Algorithm -- 3.1 The Algorithm -- 3.2 Proof of Correctness -- 3.3 Running Time Analysis -- 3.4 Space Complexity Analysis -- 4 Lower Bound -- References -- Sparse Approximation over the Cube -- 1 Introduction and Literature Review -- 2 Preliminaries -- 3 The l1-Relaxation for Random Targets b -- 4 Proximity Between Optimal Solutions of ([P0]P0) and ([P1]P1) -- 5 A Deterministic Algorithm -- 6 Extension -- References -- Recycling Inequalities for Robust Combinatorial Optimization with Budget Uncertainty -- 1 Introduction -- 2 Recycling Valid Inequalities -- 3 Facet-Defining Recycled Inequalities -- 4 Computational Study -- 4.1 Robust Independent Set -- 4.2 Robust Bipartite Matching -- 5 Conclusion -- References -- Inapproximability of Shortest Paths on Perfect Matching Polytopes -- 1 Introduction -- 1.1 Our Result -- 1.2 Pivot Rules for Circuit-Augmentation Algorithms -- 1.3 Related Works -- 2 Proof of Theorem 1.
2.1 Preliminaries -- 2.2 Reduction -- 2.3 Proof of Lemma 3 -- References -- Monoidal Strengthening and Unique Lifting in MIQCPs -- 1 Introduction -- 2 Monoidal Strengthening in the Homogeneous Case -- 3 Monoidal Strengthening in the Non-homogeneous Case -- 3.1 A Technical Consideration for Sg -- 3.2 Monoid Construction -- 4 Solving the Monoidal Strengthening Problem -- 5 Unique Lifting -- 6 Computational Results -- References -- From Approximate to Exact Integer Programming -- 1 Introduction -- 1.1 Contributions of This Paper -- 1.2 Related Work -- 2 Preliminaries -- 3 The Cut-Or-Average Algorithm -- 3.1 Bounding the Number of Iterations -- 3.2 Correctness and Efficiency of Subroutines -- 3.3 Conclusion on the Cut-Or-Average Algorithm -- 4 An Asymmetric Approximate Carathéodory Theorem -- 5 IPs with Polynomial Variable Range -- References -- Optimizing Low Dimensional Functions over the Integers -- 1 Introduction -- 1.1 Applications -- 1.2 Overview of Techniques -- 2 Non-negative Variables -- 3 Bounded Variables -- 4 Overview of Hunkenschröder Et Al. ch9hunkenschroder2022optimizing and Related Improvements -- 5 Conclusion and Open Questions -- References -- Configuration Balancing for Stochastic Requests -- 1 Introduction -- 1.1 Our Results -- 1.2 Technical Overview -- 1.3 Related Work -- 2 Configuration Balancing with Stochastic Requests -- 2.1 Structural Theorem -- 2.2 Offline Setting -- 2.3 Online Setting -- 3 Load Balancing on Related Machines -- References -- An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem -- 1 Introduction -- 2 Preliminaries -- 2.1 Optimal Solutions and Proximity -- 2.2 The Centroid Mapping -- 3 The Update-and-Stabilize Framework -- 4 Analysis -- 5 Computational Experiments -- References -- Stabilization of Capacitated Matching Games -- 1 Introduction -- 2 Preliminaries and Notation -- 3 M-vertex-stabilizer. 4 Vertex-Stabilizer -- 5 Capacitated Cooperative Matching Games -- References -- Designing Optimization Problems with Diverse Solutions -- 1 Introduction -- 2 Statement of Main Results -- 2.1 The Cyclic Polytope -- 2.2 Results and Techniques -- 3 Preliminaries -- 4 Upper Bound (Proof of Theorem 1) -- 5 General Lower Bound (Proof of Theorem 2) -- 5.1 Construction Based on Moment Curve -- 5.2 Dual Certificate for Loadouts -- 5.3 Counting the Number of k-Loadouts -- 6 Conclusion -- References -- ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation -- 1 Introduction -- 1.1 Our Main Results -- 1.2 Discussion of the Results -- 1.3 Further Related Work -- 2 Algorithms and Proof Overview -- References -- On the Correlation Gap of Matroids -- 1 Introduction -- 1.1 Our Techniques -- 2 Preliminaries -- 3 Locating the Correlation Gap -- 4 Lower Bounding the Correlation Gap -- 4.1 Lower Bounding G(x*) -- 4.2 Lower Bounding H(x*) -- 4.3 Putting Everything Together -- References -- A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP -- 1 Introduction -- 2 Preliminaries -- 3 Proof of Theorem 1 -- 4 Conclusion and Open Questions -- References -- The Polyhedral Geometry of Truthful Auctions -- 1 Introduction -- 2 Preliminaries -- 3 Characterization of One-Player Mechanisms -- 4 Sensitivity of Mechanisms -- 5 Conclusion -- References -- Competitive Kill-and-Restart and Preemptive Strategies for Non-clairvoyant Scheduling -- 1 Introduction -- 2 Preliminaries -- 3 Lower Bound -- 4 The b-scaling Strategy -- 4.1 The Deterministic b-scaling Strategy -- 4.2 The Randomized b-scaling Strategy -- 5 Weighted Shortest Elapsed Time First -- 6 Upper Bounds for More General Settings -- 7 Conclusion -- References -- A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP -- 1 Introduction -- 1.1 High Level Proof Overview. 2 Preliminaries -- 2.1 Notation -- 2.2 Randomized Algorithm of ch19KKO21a -- 2.3 Polyhedral Background -- 3 Computing Probabilities -- 3.1 Notation -- 3.2 Matrix Tree Theorem -- 3.3 Computing Parities in a Simple Case -- 4 A Deterministic Algorithm in the Degree Cut Case -- 5 General Case -- References -- Monoidal Strengthening of Simple V-Polyhedral Disjunctive Cuts -- 1 Introduction -- 2 Notation and Background -- 3 Correspondence Between PRLP and CGLP Solutions -- 3.1 Simple VPCs -- 3.2 Relaxations Without Primal Degeneracy -- 3.3 Relaxations with Primal Degeneracy -- 4 Computational Experiments -- 5 Choosing a Relaxation Amenable to Strengthening -- 6 Conclusion -- References -- Optimal General Factor Problem and Jump System Intersection -- 1 Introduction -- 1.1 General Factor Problem -- 1.2 Jump System Intersection -- 1.3 Our Contribution: Jump System with SBO Property -- 1.4 Organization -- 2 Preliminaries -- 3 Algorithm and Correctness -- 4 Outline of the Proof of Lemma 1 -- 4.1 Minimal Counterexample -- 4.2 Part of Case Analysis: |U|=3 -- 5 Extension to Valuated Problem -- 6 Weighted Optimal General Factor Problem -- 7 Concluding Remarks -- References -- Decomposition of Probability Marginals for Security Games in Abstract Networks -- 1 Introduction -- 1.1 Motivation -- 1.2 Abstract Networks -- 1.3 Previous Results -- 1.4 Our Results -- 1.5 Notation -- 2 Feasible Decompositions in Abstract Networks -- 3 Computing Feasible Decompositions -- 4 Computing Shortest Paths in Abstract Networks -- 5 Dahan et al.'s Network Security Game -- 6 The Conservation Law for Partially Ordered Sets -- 7 Other Set Systems -- References -- Set Selection Under Explorable Stochastic Uncertainty via Covering Techniques -- 1 Introduction -- 2 Algorithmic Framework -- 2.1 Offline Problems and Hardness of Approximation -- 2.2 Algorithmic Framework. 3 MinSet with Deterministic Right-Hand Sides -- 4 MinSet Under Uncertainty -- 5 Disjoint MinSet -- References -- Towards a Characterization of Maximal Quadratic-Free Sets -- 1 Introduction -- 1.1 Contributions -- 2 Examples of Maximal Homogeneous Quadratic-Free Sets -- 3 A Proof of Theorem 5 -- 4 A Proof of Theorem 1 -- 5 A Proof of Theorem 2 -- 6 Preliminary Results on Non-expansive Functions -- 7 A Proof of Theorem 3 -- 8 A Proof of Theorem 4 -- References -- Compressing Branch-and-Bound Trees -- 1 Introduction -- 2 The Tree Compression Problem (TCP) -- 3 Complexity Results and Lower Bounds -- 4 Compression Algorithms -- 4.1 An Exact Method -- 4.2 A Heuristic Method -- 5 Computational Experiments -- 5.1 Methodology -- 5.2 Full Strong Branching Results -- 5.3 Reliability Branching with Plunging -- 6 Future Work -- References -- Exploiting the Polyhedral Geometry of Stochastic Linear Bilevel Programming -- 1 Introduction -- 1.1 Problem Formulation and Contributions -- 2 Preliminaries -- 3 Vertex-Supported Beliefs and Bayesian Formulation -- 3.1 Sample Average Formulation -- 4 Geometrical Structure of Vertex-Supported Beliefs -- 5 Algorithms -- 5.1 Enumeration Algorithm -- 5.2 Monte-Carlo Approximation Scheme -- 6 Numerical Experiments -- References -- Towards an Optimal Contention Resolution Scheme for Matchings -- 1 Introduction -- 1.1 Our Results -- 1.2 Our Techniques -- 2 An Optimal CRS When "026B30D x"026B30D 0 -- 2.1 The Karp-Sipser Algorithm -- 2.2 Random Trees -- 2.3 The Karp-Sipser Algorithm on Trees -- 2.4 Putting It Together -- 3 Improved CRSs for Bipartite Matchings -- 3.1 A 0.480-Balanced Scheme for Bipartite Matchings -- 3.2 A 0.509-Balanced Scheme for Bipartite Matchings -- References -- Advances on Strictly -Modular IPs -- 1 Introduction -- 1.1 Group-Constrained Problems and Proof Strategy for Theorem 1 -- 1.2 Further Related Work. 1.3 Structure of the Paper. |
| Record Nr. | UNISA-996534465903316 |
Del Pia Alberto
|
||
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2023 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Integer Programming and Combinatorial Optimization : 24th International Conference, IPCO 2023, Madison, WI, USA, June 21–23, 2023, Proceedings / / edited by Alberto Del Pia, Volker Kaibel
| Integer Programming and Combinatorial Optimization : 24th International Conference, IPCO 2023, Madison, WI, USA, June 21–23, 2023, Proceedings / / edited by Alberto Del Pia, Volker Kaibel |
| Autore | Del Pia Alberto |
| Edizione | [1st ed. 2023.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2023 |
| Descrizione fisica | 1 online resource (494 pages) |
| Disciplina | 519.77 |
| Altri autori (Persone) | KaibelVolker |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Computer science - Mathematics
Mathematics - Data processing Discrete mathematics Application software Mathematics of Computing Computational Mathematics and Numerical Analysis Discrete Mathematics in Computer Science Computer and Information Systems Applications |
| ISBN | 9783031327261 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Contents -- Information Complexity of Mixed-Integer Convex Optimization -- 1 First-order Information Complexity -- 1.1 Our Results -- 1.2 Formal Definitions and Statement of Results -- 1.3 Discussion and Future Avenues -- 2 Proof Sketches -- 2.1 Proof Sketch of Theorem 1 -- 2.2 Proof of Theorem 3 -- 2.3 Proof Sketch of Theorem 5 -- 2.4 Proof Sketch of Theorems 2 and 4 -- References -- Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products -- 1 Introduction -- 2 RLT for Bilinear Products -- 3 Detection of Implicit Products -- 4 Separation Algorithm -- 4.1 Row Marking -- 4.2 Projection Filtering -- 5 Computational Results -- 5.1 Setup -- 5.2 Impact of RLT Cuts -- 5.3 Separation -- 5.4 Experiments with Gurobi -- 5.5 Summary -- References -- A Nearly Optimal Randomized Algorithm for Explorable Heap Selection -- 1 Introduction -- 2 The Explorable Heap Selection Problem -- 3 A New Algorithm -- 3.1 The Algorithm -- 3.2 Proof of Correctness -- 3.3 Running Time Analysis -- 3.4 Space Complexity Analysis -- 4 Lower Bound -- References -- Sparse Approximation over the Cube -- 1 Introduction and Literature Review -- 2 Preliminaries -- 3 The l1-Relaxation for Random Targets b -- 4 Proximity Between Optimal Solutions of ([P0]P0) and ([P1]P1) -- 5 A Deterministic Algorithm -- 6 Extension -- References -- Recycling Inequalities for Robust Combinatorial Optimization with Budget Uncertainty -- 1 Introduction -- 2 Recycling Valid Inequalities -- 3 Facet-Defining Recycled Inequalities -- 4 Computational Study -- 4.1 Robust Independent Set -- 4.2 Robust Bipartite Matching -- 5 Conclusion -- References -- Inapproximability of Shortest Paths on Perfect Matching Polytopes -- 1 Introduction -- 1.1 Our Result -- 1.2 Pivot Rules for Circuit-Augmentation Algorithms -- 1.3 Related Works -- 2 Proof of Theorem 1.
2.1 Preliminaries -- 2.2 Reduction -- 2.3 Proof of Lemma 3 -- References -- Monoidal Strengthening and Unique Lifting in MIQCPs -- 1 Introduction -- 2 Monoidal Strengthening in the Homogeneous Case -- 3 Monoidal Strengthening in the Non-homogeneous Case -- 3.1 A Technical Consideration for Sg -- 3.2 Monoid Construction -- 4 Solving the Monoidal Strengthening Problem -- 5 Unique Lifting -- 6 Computational Results -- References -- From Approximate to Exact Integer Programming -- 1 Introduction -- 1.1 Contributions of This Paper -- 1.2 Related Work -- 2 Preliminaries -- 3 The Cut-Or-Average Algorithm -- 3.1 Bounding the Number of Iterations -- 3.2 Correctness and Efficiency of Subroutines -- 3.3 Conclusion on the Cut-Or-Average Algorithm -- 4 An Asymmetric Approximate Carathéodory Theorem -- 5 IPs with Polynomial Variable Range -- References -- Optimizing Low Dimensional Functions over the Integers -- 1 Introduction -- 1.1 Applications -- 1.2 Overview of Techniques -- 2 Non-negative Variables -- 3 Bounded Variables -- 4 Overview of Hunkenschröder Et Al. ch9hunkenschroder2022optimizing and Related Improvements -- 5 Conclusion and Open Questions -- References -- Configuration Balancing for Stochastic Requests -- 1 Introduction -- 1.1 Our Results -- 1.2 Technical Overview -- 1.3 Related Work -- 2 Configuration Balancing with Stochastic Requests -- 2.1 Structural Theorem -- 2.2 Offline Setting -- 2.3 Online Setting -- 3 Load Balancing on Related Machines -- References -- An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem -- 1 Introduction -- 2 Preliminaries -- 2.1 Optimal Solutions and Proximity -- 2.2 The Centroid Mapping -- 3 The Update-and-Stabilize Framework -- 4 Analysis -- 5 Computational Experiments -- References -- Stabilization of Capacitated Matching Games -- 1 Introduction -- 2 Preliminaries and Notation -- 3 M-vertex-stabilizer. 4 Vertex-Stabilizer -- 5 Capacitated Cooperative Matching Games -- References -- Designing Optimization Problems with Diverse Solutions -- 1 Introduction -- 2 Statement of Main Results -- 2.1 The Cyclic Polytope -- 2.2 Results and Techniques -- 3 Preliminaries -- 4 Upper Bound (Proof of Theorem 1) -- 5 General Lower Bound (Proof of Theorem 2) -- 5.1 Construction Based on Moment Curve -- 5.2 Dual Certificate for Loadouts -- 5.3 Counting the Number of k-Loadouts -- 6 Conclusion -- References -- ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation -- 1 Introduction -- 1.1 Our Main Results -- 1.2 Discussion of the Results -- 1.3 Further Related Work -- 2 Algorithms and Proof Overview -- References -- On the Correlation Gap of Matroids -- 1 Introduction -- 1.1 Our Techniques -- 2 Preliminaries -- 3 Locating the Correlation Gap -- 4 Lower Bounding the Correlation Gap -- 4.1 Lower Bounding G(x*) -- 4.2 Lower Bounding H(x*) -- 4.3 Putting Everything Together -- References -- A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP -- 1 Introduction -- 2 Preliminaries -- 3 Proof of Theorem 1 -- 4 Conclusion and Open Questions -- References -- The Polyhedral Geometry of Truthful Auctions -- 1 Introduction -- 2 Preliminaries -- 3 Characterization of One-Player Mechanisms -- 4 Sensitivity of Mechanisms -- 5 Conclusion -- References -- Competitive Kill-and-Restart and Preemptive Strategies for Non-clairvoyant Scheduling -- 1 Introduction -- 2 Preliminaries -- 3 Lower Bound -- 4 The b-scaling Strategy -- 4.1 The Deterministic b-scaling Strategy -- 4.2 The Randomized b-scaling Strategy -- 5 Weighted Shortest Elapsed Time First -- 6 Upper Bounds for More General Settings -- 7 Conclusion -- References -- A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP -- 1 Introduction -- 1.1 High Level Proof Overview. 2 Preliminaries -- 2.1 Notation -- 2.2 Randomized Algorithm of ch19KKO21a -- 2.3 Polyhedral Background -- 3 Computing Probabilities -- 3.1 Notation -- 3.2 Matrix Tree Theorem -- 3.3 Computing Parities in a Simple Case -- 4 A Deterministic Algorithm in the Degree Cut Case -- 5 General Case -- References -- Monoidal Strengthening of Simple V-Polyhedral Disjunctive Cuts -- 1 Introduction -- 2 Notation and Background -- 3 Correspondence Between PRLP and CGLP Solutions -- 3.1 Simple VPCs -- 3.2 Relaxations Without Primal Degeneracy -- 3.3 Relaxations with Primal Degeneracy -- 4 Computational Experiments -- 5 Choosing a Relaxation Amenable to Strengthening -- 6 Conclusion -- References -- Optimal General Factor Problem and Jump System Intersection -- 1 Introduction -- 1.1 General Factor Problem -- 1.2 Jump System Intersection -- 1.3 Our Contribution: Jump System with SBO Property -- 1.4 Organization -- 2 Preliminaries -- 3 Algorithm and Correctness -- 4 Outline of the Proof of Lemma 1 -- 4.1 Minimal Counterexample -- 4.2 Part of Case Analysis: |U|=3 -- 5 Extension to Valuated Problem -- 6 Weighted Optimal General Factor Problem -- 7 Concluding Remarks -- References -- Decomposition of Probability Marginals for Security Games in Abstract Networks -- 1 Introduction -- 1.1 Motivation -- 1.2 Abstract Networks -- 1.3 Previous Results -- 1.4 Our Results -- 1.5 Notation -- 2 Feasible Decompositions in Abstract Networks -- 3 Computing Feasible Decompositions -- 4 Computing Shortest Paths in Abstract Networks -- 5 Dahan et al.'s Network Security Game -- 6 The Conservation Law for Partially Ordered Sets -- 7 Other Set Systems -- References -- Set Selection Under Explorable Stochastic Uncertainty via Covering Techniques -- 1 Introduction -- 2 Algorithmic Framework -- 2.1 Offline Problems and Hardness of Approximation -- 2.2 Algorithmic Framework. 3 MinSet with Deterministic Right-Hand Sides -- 4 MinSet Under Uncertainty -- 5 Disjoint MinSet -- References -- Towards a Characterization of Maximal Quadratic-Free Sets -- 1 Introduction -- 1.1 Contributions -- 2 Examples of Maximal Homogeneous Quadratic-Free Sets -- 3 A Proof of Theorem 5 -- 4 A Proof of Theorem 1 -- 5 A Proof of Theorem 2 -- 6 Preliminary Results on Non-expansive Functions -- 7 A Proof of Theorem 3 -- 8 A Proof of Theorem 4 -- References -- Compressing Branch-and-Bound Trees -- 1 Introduction -- 2 The Tree Compression Problem (TCP) -- 3 Complexity Results and Lower Bounds -- 4 Compression Algorithms -- 4.1 An Exact Method -- 4.2 A Heuristic Method -- 5 Computational Experiments -- 5.1 Methodology -- 5.2 Full Strong Branching Results -- 5.3 Reliability Branching with Plunging -- 6 Future Work -- References -- Exploiting the Polyhedral Geometry of Stochastic Linear Bilevel Programming -- 1 Introduction -- 1.1 Problem Formulation and Contributions -- 2 Preliminaries -- 3 Vertex-Supported Beliefs and Bayesian Formulation -- 3.1 Sample Average Formulation -- 4 Geometrical Structure of Vertex-Supported Beliefs -- 5 Algorithms -- 5.1 Enumeration Algorithm -- 5.2 Monte-Carlo Approximation Scheme -- 6 Numerical Experiments -- References -- Towards an Optimal Contention Resolution Scheme for Matchings -- 1 Introduction -- 1.1 Our Results -- 1.2 Our Techniques -- 2 An Optimal CRS When "026B30D x"026B30D 0 -- 2.1 The Karp-Sipser Algorithm -- 2.2 Random Trees -- 2.3 The Karp-Sipser Algorithm on Trees -- 2.4 Putting It Together -- 3 Improved CRSs for Bipartite Matchings -- 3.1 A 0.480-Balanced Scheme for Bipartite Matchings -- 3.2 A 0.509-Balanced Scheme for Bipartite Matchings -- References -- Advances on Strictly -Modular IPs -- 1 Introduction -- 1.1 Group-Constrained Problems and Proof Strategy for Theorem 1 -- 1.2 Further Related Work. 1.3 Structure of the Paper. |
| Record Nr. | UNINA-9910726288203321 |
|
Del Pia Alberto
|
||
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2023 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Integer Programming and Combinatorial Optimization [[electronic resource] ] : 11th International IPCO Conference, Berlin, Germany, June 8-10, 2005, Proceedings / / edited by Michael Jünger, Volker Kaibel
| Integer Programming and Combinatorial Optimization [[electronic resource] ] : 11th International IPCO Conference, Berlin, Germany, June 8-10, 2005, Proceedings / / edited by Michael Jünger, Volker Kaibel |
| Edizione | [1st ed. 2005.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 |
| Descrizione fisica | 1 online resource (XII, 488 p.) |
| Disciplina | 519.77 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science—Mathematics
Discrete mathematics Numerical analysis Algorithms Computer graphics Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics |
| ISBN | 9783540321026 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Mixed-Integer Cuts from Cyclic Groups -- Optimizing over the First Chvàtal Closure -- Sequential Pairing of Mixed Integer Inequalities -- Approximate Min-max Relations for Odd Cycles in Planar Graphs -- Disjoint Cycles: Integrality Gap, Hardness, and Approximation -- A Combinatorial Algorithm to Find a Maximum Even Factor -- Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems -- On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem -- Inventory and Facility Location Models with Market Selection -- On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations -- Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials -- Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring -- On the Inefficiency of Equilibria in Congestion Games -- Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times -- LP-Based Online Scheduling: From Single to Parallel Machines -- Unique Sink Orientations of Grids -- Jumping Doesn’t Help in Abstract Cubes -- Computing the Inertia from Sign Patterns -- Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem -- On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem -- Smoothed Analysis of Integer Programming -- Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs -- Approximation Algorithms for Stochastic Inventory Control Models -- On Two-Stage Stochastic Minimum Spanning Trees -- Combinatorial Analysis of Generic Matrix Pencils -- Power Optimization for Connectivity Problems -- Packing Steiner Forests -- Bidimensional Packing by Bilinear Programming -- On the L ???-Norm of Extreme Points for Crossing Supermodular Directed Network LPs -- Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks -- Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem -- Using Grammars to Generate Very Large Scale Neighborhoods for the Traveling Salesman Problem and Other Sequencing Problems -- A Study of Domino-Parity and k-Parity Constraints for the TSP -- Not Every GTSP Facet Induces an STSP Facet. |
| Record Nr. | UNISA-996466121203316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Integer Programming and Combinatorial Optimization : 11th International IPCO Conference, Berlin, Germany, June 8-10, 2005, Proceedings / / edited by Michael Jünger, Volker Kaibel
| Integer Programming and Combinatorial Optimization : 11th International IPCO Conference, Berlin, Germany, June 8-10, 2005, Proceedings / / edited by Michael Jünger, Volker Kaibel |
| Edizione | [1st ed. 2005.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 |
| Descrizione fisica | 1 online resource (XII, 488 p.) |
| Disciplina | 519.77 |
| Altri autori (Persone) |
JüngerM (Michael)
KaibelVolker |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science - Mathematics
Discrete mathematics Numerical analysis Algorithms Computer graphics Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics |
| ISBN | 9783540321026 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Mixed-Integer Cuts from Cyclic Groups -- Optimizing over the First Chvàtal Closure -- Sequential Pairing of Mixed Integer Inequalities -- Approximate Min-max Relations for Odd Cycles in Planar Graphs -- Disjoint Cycles: Integrality Gap, Hardness, and Approximation -- A Combinatorial Algorithm to Find a Maximum Even Factor -- Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems -- On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem -- Inventory and Facility Location Models with Market Selection -- On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations -- Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials -- Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring -- On the Inefficiency of Equilibria in Congestion Games -- Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times -- LP-Based Online Scheduling: From Single to Parallel Machines -- Unique Sink Orientations of Grids -- Jumping Doesn’t Help in Abstract Cubes -- Computing the Inertia from Sign Patterns -- Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem -- On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem -- Smoothed Analysis of Integer Programming -- Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs -- Approximation Algorithms for Stochastic Inventory Control Models -- On Two-Stage Stochastic Minimum Spanning Trees -- Combinatorial Analysis of Generic Matrix Pencils -- Power Optimization for Connectivity Problems -- Packing Steiner Forests -- Bidimensional Packing by Bilinear Programming -- On the L???-Norm of Extreme Points for Crossing Supermodular Directed Network LPs -- Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks -- Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem -- Using Grammars to Generate Very Large Scale Neighborhoods for the Traveling Salesman Problem and Other Sequencing Problems -- A Study of Domino-Parity and k-Parity Constraints for the TSP -- Not Every GTSP Facet Induces an STSP Facet. |
| Record Nr. | UNINA-9910483180603321 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||