Integer Programming and Combinatorial Optimization

Name: Integer Programming and Combinatorial Optimization | 24th International Conference, IPCO 2023, Madison, WI, USA, June 21-23, 2023, Proceedings
Brand: Springer
Price: 85.59 EUR
Availability: OnlineOnly

24th International Conference, IPCO 2023, Madison, WI, USA, June 21-23, 2023, Proceedings

Alberto Del Pia Volker Kaibel(Herausgeber*in)

Springer (Verlag)

Erschienen am 21. Mai 2023

XIII, 482 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-031-32726-1 (ISBN)

85,59 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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
2 GCTUF with Transposed Network Constraint Matrices
3 Overview of Our Techniques Leading to Theorem 3
3.1 Reducing to a Simpler Problem When the Target Elements Form a Union of Cosets
3.2 Decomposing the Problem
3.3 Handling Patterns
References
Cut-Sufficient Directed 2-Commodity Multiflow Topologies
1 Introduction
1.1 Other Related Work
2 Preliminaries
2.1 Cut-Deceptive Weights and Minors of Multiflow Topologies
3 Relevant Minors and Entry-Exit Connected Edge Sets
3.1 Relevant Minors
3.2 Contractions of Entry-Exit Connected Sets
4 Characterizations of Cut-Sufficiency
4.1 Opposingly Ordered Paths
4.2 Characterization for Roundtrip and Two-Path Demands
5 NP-Hardness of Recognizing Cut-Sufficiency
6 Towards a Complete 2-Commodity Characterization
References
Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid
1 Introduction
2 Random-Assignment MSP and Densities
3 Outline of Our Approach
3.1 Rank-Density Curves
3.2 Proof Plan for Theorem1 via Rank-Density Curves
4 Learning Rank-Density Curves from a Sample
5 The Main Algorithm and Its Analysis
5.1 Proof (Sketch) of Theorem5
References
A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints
1 Introduction
2 A Combinatorial Algorithm for BKP
2.1 The Bound Test
2.2 Computing Initial Bounds
3 Lower Bound
4 Computational Results
4.1 Implementation
4.2 Instances
4.3 Results
5 Conclusion
References
Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
1 Introduction
1.1 Dynamic Matching Algorithms
1.2 Linear Program for MWM
1.3 Multiplicative Weight Updates for Packing LPs
1.4 Auction Algorithms
1.5 Our Contribution
2 The Static Algorithm
2.1 Improving the Running Time
3 Dynamic Algorithm
A Combinatorial proof of Lemma 2
References
A Linear Time Algorithm for Linearizing Quadratic and Higher-Order Shortest Path Problems
1 Introduction
2 Notations and Preliminaries
3 A Characterization of Linearizable Instances of the GSPP on Acyclic Digraphs
4 A Linear Time Algorithm for the LinSPPd
4.1 The All Paths Equal Cost Problem of Order-d (APECPd)
4.2 The Linear Time LinSPPd algorithm
5 The Subspace of Linearizable Instances
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken