LP-based algorithms for multistage minimization problems

DOI10.1007/978-3-030-80879-2_1MaRDI QIDQ2117680zbMATH OpenOpenAlexFDO

Authors Evripidis Bampis, Bruno Escoffier, Alexander Kononov

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

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

Cites work

• scientific article; zbMATH DE number 7561666 (Why is no real title available?)
• scientific article; zbMATH DE number 7238962 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A note on the prize collecting traveling salesman problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Changing bases: multistage optimization for matroids and matchings
• Competitive analysis via regularization
• Dynamic facility location via exponential clocks
• Facility location in evolving metrics
• Heuristic analysis, linear programming and branch and bound
• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• Multistage Vertex Cover
• Offline and online facility leasing
• Online multistage subset maximization problems
• Reallocating multiple facilities on the line
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The design of approximation algorithms
• The itinerant list update problem
• The power of deferral: maintaining a constant-competitive Steiner tree online
• The power of recourse for online MST and TSP
• The prize collecting traveling salesman problem
• Unified algorithms for online learning and competitive analysis

Cited in

(5)

• Multistage \(s-t\) path: confronting similarity with dissimilarity
• Approximating multistage matching problems
• A simple rounding scheme for multistage optimization
• Multistage vertex cover
• Cluster editing for multi-layer and temporal graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117680)