Show simple item record

dc.contributor.author
Grunau, Christoph
dc.contributor.author
Mitrović, Slobodan
dc.contributor.author
Rubinfeld, Ronitt
dc.contributor.author
Vakilian, Ali
dc.date.accessioned
2020-09-08T06:53:43Z
dc.date.available
2020-08-20T09:41:43Z
dc.date.available
2020-09-08T06:53:43Z
dc.date.issued
2020-01
dc.identifier.uri
http://hdl.handle.net/20.500.11850/432106
dc.description.abstract
We design a Local Computation Algorithm (LCA) for the set cover problem. Given a set system where each set has size at most s and each element is contained in at most t sets, the algorithm reports whether a given set is in some fixed set cover whose expected size is O(log s) times the minimum fractional set cover value. Our algorithm requires s(O(log s))t(O(log s.(log log s+log log t))) queries. This result improves upon the application of the reduction of [Parnas and Ron, TCS'07] on the result of [Kuhn et al., SODA'06], which leads to a query complexity of (st)(O(log s.log t)). To obtain this result, we design a parallel set cover algorithm that admits an efficient simulation in the LCA model by using a sparsification technique introduced in [Ghaffari and Uitto, SODA'19] for the maximal independent set problem. The parallel algorithm adds a random subset of the sets to the solution in a style similar to the PRAM algorithm of [Berger et al., FOCS'89]. However, our algorithm differs in the way that it never revokes its decisions, which results in a fewer number of adaptive rounds. This requires a novel approximation analysis which might be of independent interest.
en_US
dc.language.iso
en
en_US
dc.publisher
SIAM
dc.title
Improved Local Computation Algorithm for Set Cover via Sparsification
en_US
dc.type
Conference Paper
ethz.book.title
SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms
en_US
ethz.pages.start
2993
en_US
ethz.pages.end
3011
en_US
ethz.event
31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
en_US
ethz.event.location
Salt Lake City, UT, USA
ethz.event.date
January 5-8, 2020
ethz.identifier.wos
ethz.publication.place
Philadelphia, PA
ethz.publication.status
published
en_US
ethz.date.deposited
2020-08-20T09:41:54Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2020-09-08T06:53:56Z
ethz.rosetta.lastUpdated
2024-02-02T11:59:45Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Improved%20Local%20Computation%20Algorithm%20for%20Set%20Cover%20via%20Sparsification&rft.date=2020-01&rft.spage=2993&rft.epage=3011&rft.au=Grunau,%20Christoph&Mitrovi%C4%87,%20Slobodan&Rubinfeld,%20Ronitt&Vakilian,%20Ali&rft.genre=proceeding&rft.btitle=SODA%20'20:%20Proceedings%20of%20the%20Thirty-First%20Annual%20ACM-SIAM%20Symposium%20on%20Discrete%20Algorithms
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record