Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 8784))
Included in the following conference series:
1707Accesses
Abstract
We develop the first streaming algorithm and the first two-party communication protocol that uses a constant number of passes/rounds and sublinear space/communication for logarithmic approximation to the classic Set Cover problem. Specifically, forn elements andm sets, our algorithm/protocol achieves a space bound ofO(m ·nδlog2n logm) usingO(41/δ) passes/rounds while achieving an approximation factor ofO(41/δ logn) in polynomial time (forδ = Ω(1/logn)). If we allow the algorithm/protocol to spend exponential time per pass/round, we achieve an approximation factor ofO(41/δ). Our approach uses randomization, which we show is necessary: no deterministic constant approximation is possible (even given exponential time) usingo(mn) space. These results are some of the first on streaming algorithms and efficient two-party communication protocols for approximation algorithms. Moreover, we show that our algorithm can be applied to multi-party communication model.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms 2(2), 153–177 (2006)
Chierichetti, F., Kumar, R., Tomkins, A.: Max-cover in map-reduce. In: Proc. of WWW, pp. 231–240. ACM (2010)
Cormode, G., Karloff, H., Wirth, A.: Set cover algorithms for very large datasets. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management, pp. 479–488. ACM (2010)
Dolev, D., Feder, T.: Multiparty communication complexity. In: Proc. of IEEE FOCS, pp. 428–433. IEEE (1989)
Ďuriš, P., Rolim, J.D.P.: Lower bounds on the multiparty communication complexity. Journal of Computer and System Sciences 56(1), 90–95 (1998)
Emek, Y., Rosén, A.: Semi-streaming set cover. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. Part I. LNCS, vol. 8572, pp. 453–464. Springer, Heidelberg (2014)
Grossman, T., Wool, A.: Computational experience with approximation algorithms for the set covering problem. European Journal of Operational Research 101(1), 81–92 (1997)
Guha, S., McGregor, A.: Tight lower bounds for multi-pass stream computation via pass elimination. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 760–772. Springer, Heidelberg (2008)
Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in mapreduce and streaming. In: Proc. of SPAA, pp. 1–10. ACM (2013)
Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. Journal of the ACM 41(5), 960–981 (1994)
Nisan, N.: The communication complexity of approximate set packing and covering. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 868–875. Springer, Heidelberg (2002)
Phillips, J.M., Verbin, E., Zhang, Q.: Lower bounds for number-in-hand multiparty communication complexity, made easy. In: Proc. of ACM-SIAM SODA, pp. 486–501. SIAM (2012)
Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability pcp characterization of np. In: Proc. of ACM STOC, pp. 475–484. ACM (1997)
Saha, B., Getoor, L.: On maximum coverage in the streaming model & application to multi-topic blog-watch. In: SDM, pp. 697–708 (2009)
Woodruff, D.P., Zhang, Q.: When distributed computation is communication expensive. In: Afek, Y. (ed.) DISC 2013. LNCS, vol. 8205, pp. 16–30. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Massachusetts Instittute of Technology (MIT), USA
Erik D. Demaine, Piotr Indyk, Sepideh Mahabadi & Ali Vakilian
- Erik D. Demaine
You can also search for this author inPubMed Google Scholar
- Piotr Indyk
You can also search for this author inPubMed Google Scholar
- Sepideh Mahabadi
You can also search for this author inPubMed Google Scholar
- Ali Vakilian
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Department of Computer Science, University of Freiburg, 79110, Freiburg, Germany
Fabian Kuhn
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Demaine, E.D., Indyk, P., Mahabadi, S., Vakilian, A. (2014). On Streaming and Communication Complexity of the Set Cover Problem. In: Kuhn, F. (eds) Distributed Computing. DISC 2014. Lecture Notes in Computer Science, vol 8784. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45174-8_33
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-662-45173-1
Online ISBN:978-3-662-45174-8
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative