Tight Bounds for Double Coverage Against Weak Adversaries

DOI10.1007/978-3-319-28684-6_5MaRDI QIDQ2788990zbMATH OpenOpenAlexFDO

Authors N. Bansal, Marek Eliáš, Łukasz Jeż, Grigorios Koumoutsos, Kirk Pruhs

Publication date 26 February 2016

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://ir.cwi.nl/pub/28330

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Recommendations

• Tight bounds for double coverage against weak adversaries
• Tight approximation bounds for maximum multi-coverage
• Tight approximation bounds for maximum multi-coverage
• Unbounded lower bound for k-server against weak adversaries
• Tight bounds on the round complexity of the distributed maximum coverage problem
• Tight approximation bounds for combinatorial frugal coverage algorithms
• Tight approximation bounds for greedy frugal coverage algorithms
• Lower bounds for restricted schemes in the two-adaptive bitprobe model
• A Tight Bound for Stochastic Submodular Cover
• A class of problems where dual bounds beat underestimation bounds

Cited in

(2)

• Tight bounds for double coverage against weak adversaries
• Online \(k\)-taxi via double coverage and time-reverse primal-dual

This page was built for publication: Tight Bounds for Double Coverage Against Weak Adversaries

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