LP-based algorithms for multistage minimization problems

DOI10.1007/978-3-030-80879-2_1OpenAlexW3183892126MaRDI QIDQ2117680

Evripidis Bampis, Alexander V. Kononov, Bruno Escoffier

Publication date: 22 March 2022

Full work available at URL: https://arxiv.org/abs/1909.10354

zbMATH Keywords

approximation algorithmsLP-roundingmultistage optimization

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (4)

Multistage vertex cover ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Approximating multistage matching problems ⋮ A simple rounding scheme for multistage optimization

Cites Work

• Unnamed Item
• Unnamed Item
• A note on the prize collecting traveling salesman problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• The Itinerant List Update problem
• Offline and online facility leasing
• Online multistage subset maximization problems
• Reallocating multiple facilities on the line
• Unified Algorithms for Online Learning and Competitive Analysis
• The Design of Approximation Algorithms
• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
• The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
• The prize collecting traveling salesman problem
• Heuristic analysis, linear programming and branch and bound
• A General Approximation Technique for Constrained Forest Problems
• Dynamic Facility Location via Exponential Clocks
• Changing Bases: Multistage Optimization for Matroids and Matchings
• Facility Location in Evolving Metrics
• Competitive Analysis via Regularization
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Multistage Vertex Cover
• The Power of Recourse for Online MST and TSP

This page was built for publication: LP-based algorithms for multistage minimization problems