Online multistage subset maximization problems

DOI10.1007/S00453-021-00834-7MaRDI QIDQ2041973zbMATH OpenOpenAlexFDO

Authors Evripidis Bampis, Kevin Schewior, 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, https://drops.dagstuhl.de/opus/volltexte/2019/11132/

zbMATH Keywords

multistage optimizationonline algorithms

Mathematics Subject Classification ID

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

Recommendations

• Multistage knapsack
• Changing bases: multistage optimization for matroids and matchings
• Online submodular maximization with preemption
• Online submodular maximization with preemption
• General bounds for incremental maximization

Cites work

• A 2-competitive algorithm for online convex optimization with switching costs
• A tight lower bound for online convex optimization with switching costs
• Approximation schemes for a class of subset selection problems
• Changing bases: multistage optimization for matroids and matchings
• Competitive analysis via regularization
• Dynamic facility location via exponential clocks
• Dynamic sum-radii clustering
• Facility location in evolving metrics
• scientific article; zbMATH DE number 7525448 (Why is no real title available?)
• scientific article; zbMATH DE number 7238962 (Why is no real title available?)
• Infrastructure Leasing Problems
• Offline and online facility leasing
• On the tradeoff between stability and fit
• 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
• Unified algorithms for online learning and competitive analysis

Cited in

(11)

• LP-based algorithms for multistage minimization problems
• Multistage vertex cover
• scientific article; zbMATH DE number 1670658 (Why is no real title available?)
• scientific article; zbMATH DE number 7525448 (Why is no real title available?)
• Multistage knapsack
• Online Submodular Maximization Problem with Vector Packing Constraint.
• Online Algorithms for Multilevel Aggregation
• Changing bases: multistage optimization for matroids and matchings
• Approximating multistage matching problems
• Approximating multistage matching problems
• Online 2-stage stable matching

This page was built for publication: Online multistage subset maximization problems

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