The online min-sum set cover problem

DOI10.4230/LIPICS.ICALP.2020.51MaRDI QIDQ6842523zbMATH OpenFDO

Authors Dimitris Fotakis, L. Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, Manolis Vardas

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.51

zbMATH Keywords

competitive analysismin-sum set coveronline algorithms

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A constant factor approximation algorithm for generalized MIN-sum set cover
• A decision-theoretic generalization of on-line learning and an application to boosting
• A note on the generalized min-sum set cover problem
• A polylogarithmic-competitive algorithm for the k-server problem
• A primal-dual randomized algorithm for weighted paging
• Algorithms – ESA 2005
• An input sensitive online algorithm for the metric bipartite matching problem
• An Optimal On-Line Algorithm for K Servers on Trees
• An optimal on-line algorithm for metrical task system
• Approximating min sum set cover
• Approximation and Online Algorithms
• Chasing Convex Bodies Optimally
• Chasing Convex Bodies with Linear Competitive Ratio
• Competitive algorithms for generalized k-server in uniform metrics
• Competitive algorithms for server problems
• Fair online load balancing
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 6783452 (Why is no real title available?)
• Improved Randomized On-Line Algorithms for the List Update Problem
• Metrical task systems on trees via mirror descent and unfair gluing
• Minimum latency submodular cover
• Multiple intents re-ranking
• New Ressults on Server Problems
• On chromatic sums and distributed resource allocation
• On the k -server conjecture
• On the competitive ratio for online facility location
• On-line learning and the metrical task system problem
• Online node-weighted Steiner tree and related problems
• Preemptive and non-preemptive generalized min sum set cover
• Self-adjusting binary search trees
• Static optimality and dynamic search-optimality in lists and trees
• Stochastic online metric matching
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
• The multiplicative weights update method: a meta-algorithm and applications
• The weighted majority algorithm
• Weighted k-server bounds via combinatorial dichotomies

This page was built for publication: The online min-sum set cover problem

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