Abbildung von: Integer Programming and Combinatorial Optimization - Springer

Integer Programming and Combinatorial Optimization

24th International Conference, IPCO 2023, Madison, WI, USA, June 21-23, 2023, Proceedings
Alberto Del PiaVolker 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)
78,10 €inkl. 7% MwSt.
Systemvoraussetzungen
für PDF mit Wasserzeichen-DRM
E-Book Einzellizenz
Als Download verfügbar

This book constitutes the refereed proceedings of the 24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023, held in Madison, WI, USA, during June 21-23, 2023.

The 33 full papers presented were carefully reviewed and selected from 119 submissions. IPCO is under the auspices of the Mathematical Optimization Society, and it is an important forum for presenting present recent developments in theory, computation, and applications. The scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integer programming and combinatorial optimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.

Reihe
13904
Auflage
1st ed. 2023
Sprache
Englisch
Verlagsort
Cham
Schweiz
Verlagsgruppe
Springer International Publishing
Illustrationen
18 s/w Abbildungen, 53 farbige Abbildungen
XIII, 482 p. 71 illus., 53 illus. in color.
Schlagworte
polynomial time complexitypolynomial time algorithmscutting planesdesign of algorithmsMathematicsanalysis of algorithmsapproximation algorithmsoptimization problemsPolynomial OptimizationCombinatorial Mathematicslinear programmingComputer ScienceCombinatorial optimizationDiscrete OptimizationMixed Integer Programmingcombinatorial problemsinteger programmingMathematical OptimizationTheoretical computer sciencegraph theory
ISBN-13
978-3-031-32726-1 (9783031327261)
DOI
10.1007/978-3-031-32726-1
Schweitzer Klassifikation
Informatik / ComputerAllgemeinAlgorithmen / Datenstrukturen
Informatik / ComputerAllgemeinMathematik für Informatiker
Informatik / ComputerProgrammierung / Software EntwicklungAlgorithmen / Datenstrukturen
Thema Klassifikation
EDV und InformationstechnologieAngewandte Informatik
EDV und InformationstechnologieInformatikTheoretische InformatikMathematik für Informatiker
Mathematik und NaturwissenschaftenMathematikDiskrete Mathematik
Mathematik und NaturwissenschaftenMathematikMathematische Analysis, allgemeinNumerische Mathematik
DNB DDC Sachgruppen
Informatik
Dewey Decimal Classfication (DDC)
ScienceMathematicsProbabilities & applied mathematics
BIC 2 Klassifikation
Computing & information technologyComputer scienceMathematical theory of computation
Computing & information technologyInformation technology: general issues
Mathematics & scienceMathematicsCalculus & mathematical analysisNumerical analysis
Mathematics & scienceMathematicsDiscrete mathematics
BISAC Klassifikation
ComputersData Processing
MathematicsCounting & Numeration
Warengruppensystematik 2.0
Naturwissenschaften, Medizin, Informatik, TechnikInformatik, EDVInformatik

Andere Ausgaben

Abbildung von: Integer Programming and Combinatorial Optimization - Springer
Alberto Del Pia | Volker Kaibel
Integer Programming and Combinatorial Optimization
24th International Conference, IPCO 2023, Madison, WI, USA, June 21-23, 2023, Proceedings
Buch
05/2023
1. Auflage
Springer
79,17 €
Versand in 15-20 Tagen
  • 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

Dateiformat: PDF
Kopierschutz: Wasserzeichen-DRM (Digital Rights Management)

Systemvoraussetzungen:

  • Computer (Windows; MacOS X; Linux): Verwenden Sie zum Lesen die kostenlose Software Adobe Reader, Adobe Digital Editions oder einen anderen PDF-Viewer Ihrer Wahl (siehe E-Book Hilfe).
  • Tablet/Smartphone (Android; iOS): Installieren Sie bereits vor dem Download die kostenlose App Adobe Digital Editions oder die App PocketBook (siehe E-Book Hilfe).
  • E-Book-Reader: Bookeen, Kobo, Pocketbook, Sony, Tolino u.v.a.m. (nur bedingt: Kindle)

Das Dateiformat PDF zeigt auf jeder Hardware eine Buchseite stets identisch an. Daher ist eine PDF auch für ein komplexes Layout geeignet, wie es bei Lehr- und Fachbüchern verwendet wird (Bilder, Tabellen, Spalten, Fußnoten). Bei kleinen Displays von E-Readern oder Smartphones sind PDF leider eher nervig, weil zu viel Scrollen notwendig ist. Mit Wasserzeichen-DRM wird hier ein „weicher” Kopierschutz verwendet. Daher ist technisch zwar alles möglich – sogar eine unzulässige Weitergabe. Aber an sichtbaren und unsichtbaren Stellen wird der Käufer des E-Books als Wasserzeichen hinterlegt, sodass im Falle eines Missbrauchs die Spur zurückverfolgt werden kann.

Weitere Informationen finden Sie in unserer  E-Book Hilfe.