Set cover in sub-linear time

MaRDI QIDQ4608053zbMATH OpenFDO

Authors Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee, Piotr Indyk

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1902.03534, http://dl.acm.org/citation.cfm?id=3175463

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Tight bounds for single-pass streaming complexity of the set cover problem
• Tight bounds for single-pass streaming complexity of the set cover problem
• Semi-streaming set cover
• Semi-streaming set cover (extended abstract)
• Partial sublinear time approximation and inapproximation for maximum coverage

Cited in

(13)

• The power of an example: hidden set size approximation using group queries and conditional sampling
• Applied Cryptography and Network Security
• Approximating minimum keys and optimal substructure screens
• Partial sublinear time approximation and inapproximation for maximum coverage
• Beep-and-sleep: message and energy efficient set cover
• Beep-and-sleep: message and energy efficient set cover
• The covert set-cover problem with application to network discovery
• Tight bounds on subexponential time approximation of set cover and related problems
• Tight bounds for single-pass streaming complexity of the set cover problem
• scientific article; zbMATH DE number 2086678 (Why is no real title available?)
• scientific article; zbMATH DE number 7561379 (Why is no real title available?)
• Almost optimal query algorithm for hitting set using a subset query
• Database Theory - ICDT 2005

This page was built for publication: Set cover in sub-linear time

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