Online multistage subset maximization problems

DOI10.1007/s00453-021-00834-7OpenAlexW3165521905MaRDI QIDQ2041973

Kevin Schewior, Evripidis Bampis, Alexandre Teiller, Bruno Escoffier

Publication date: 26 July 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

online algorithmsmultistage optimization

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items

Multistage vertex cover, Online 2-stage stable matching, Approximating multistage matching problems, LP-based algorithms for multistage minimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• A tight lower bound for online convex optimization with switching costs
• The Itinerant List Update problem
• Offline and online facility leasing
• Approximation schemes for a class of subset selection problems
• Unified Algorithms for Online Learning and Competitive Analysis
• Dynamic Sum-Radii Clustering
• The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
• On the Tradeoff between Stability and Fit
• Dynamic Facility Location via Exponential Clocks
• Changing Bases: Multistage Optimization for Matroids and Matchings
• Facility Location in Evolving Metrics
• A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs
• Competitive Analysis via Regularization
• Infrastructure Leasing Problems
• The Power of Recourse for Online MST and TSP