Set cover in sub-linear time

zbMATH Open1403.68361arXiv1902.03534MaRDI QIDQ4608053FDOQ4608053

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

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

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)

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)