Document Open Access Logo

Fractional Set Cover in the Streaming Model

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

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.12.pdf
  • Filesize: 0.72 MB
  • 20 pages

Document Identifiers

Author Details

Piotr Indyk
Sepideh Mahabadi
Ronitt Rubinfeld
Jonathan Ullman
Ali Vakilian
Anak Yodpinyanee

Cite As Get BibTex

Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, and Anak Yodpinyanee. Fractional Set Cover in the Streaming Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.12

Abstract

We study the Fractional Set Cover problem in the streaming model. That is, we consider the relaxation of the set cover problem over a universe of n elements and a collection of m sets, where each set can be picked fractionally, with a value in [0,1]. We present a randomized (1+a)-approximation algorithm that makes p passes over the data, and uses O(polylog(m,n,1/a) (mn^(O(1/(pa)))+n)) memory space. The algorithm works in both the set arrival and the edge arrival models. To the best of our knowledge, this is the first streaming result for the fractional set cover problem. We obtain our results by employing the multiplicative weights update framework in the streaming settings.

Subject Classification

Keywords
  • Streaming Algorithms
  • Fractional Set Cover
  • LP relaxation
  • Multiplicative Weight Update

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. K. J. Ahn and S. Guha. Linear programming in the semi-streaming model with application to the maximum matching problem. In Proc. 38th Int'l Colloq. Automata Lang. Prog. (ICALP), pages 526-538. Springer, 2011. Google Scholar
  2. K. J. Ahn and S. Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. In Proc. 27th ACM Symp. Parallel Alg. Arch. (SPAA), pages 202-211, 2015. Google Scholar
  3. Z. Allen-Zhu and L. Orecchia. Nearly-linear time positive LP solver with faster convergence rate. In Proc. 47th Annual ACM Symp. Theory Comput. (STOC), pages 229-236, 2015. Google Scholar
  4. Z. Allen-Zhu and L. Orecchia. Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel. In Proc. 26th ACM-SIAM Symp. Discrete Algs. (SODA), pages 1439-1456, 2015. Google Scholar
  5. N. Alon, D. Moshkovitz, and S. Safra. Algorithmic construction of sets for k-restrictions. ACM Trans. Algo., 2(2):153-177, 2006. Google Scholar
  6. S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(1):121-164, 2012. Google Scholar
  7. S. Assadi. Tight space-approximation tradeoff for the multi-pass streaming set cover problem. In Proc. 36th ACM Symp. on Principles of Database Systems (PODS), pages 321-335, 2017. Google Scholar
  8. S. Assadi, S. Khanna, and Y. Li. Tight bounds for single-pass streaming complexity of the set cover problem. In Proc. 48th Annual ACM Symp. Theory Comput. (STOC), pages 698-711, 2016. Google Scholar
  9. A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, and A. Krause. Streaming submodular maximization: Massive data summarization on the fly. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 671-680, 2014. Google Scholar
  10. B. Bahmani, A. Goel, and K. Munagala. Efficient primal-dual graph algorithms for mapreduce. In International Workshop on Algorithms and Models for the Web-Graph, pages 59-78. Springer, 2014. Google Scholar
  11. N. Bansal, A. Caprara, and M. Sviridenko. A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM Journal on Computing, 39(4):1256-1278, 2009. Google Scholar
  12. M. Bateni, H. Esfandiari, and V. S. Mirrokni. Almost optimal streaming algorithms for coverage problems. Proc. 29th ACM Symp. Parallel Alg. Arch. (SPAA), 2017. Google Scholar
  13. A. Chakrabarti and A. Wirth. Incidence geometries and the pass complexity of semi-streaming set cover. In Proc. 27th ACM-SIAM Symp. Discrete Algs. (SODA), pages 1365-1373, 2016. Google Scholar
  14. C. Chekuri, S. Gupta, and K. Quanrud. Streaming algorithms for submodular function maximization. In Proc. 42st Int'l Colloq. Automata Lang. Prog. (ICALP), pages 318-330. Springer, 2015. Google Scholar
  15. F. Chierichetti, R. Kumar, and A. Tomkins. Max-cover in map-reduce. In Proc. 19th Int. Conf. World Wide Web (WWW), pages 231-240, 2010. Google Scholar
  16. G. Cormode, H. J. Karloff, and A. Wirth. Set cover algorithms for very large datasets. In Proc. 19th ACM Conf. Info. Know. Manag. (CIKM), pages 479-488, 2010. Google Scholar
  17. E. D. Demaine, P. Indyk, S. Mahabadi, and A. Vakilian. On streaming and communication complexity of the set cover problem. In Proc. 28th Int'l Symp. Dist. Comp. (DISC), volume 8784 of Lect. Notes in Comp. Sci., pages 484-498, 2014. Google Scholar
  18. I. Dinur and D. Steurer. Analytical approach to parallel repetition. In Proc. 46th Annual ACM Symp. Theory Comput. (STOC), pages 624-633. ACM, 2014. Google Scholar
  19. P. Drineas, R. Kannan, and M. W. Mahoney. Sampling sub-problems of heterogeneous max-cut problems and approximation algorithms. In Proc. 37th Annual ACM Symp. Theory Comput. (STOC), pages 57-68. Springer, 2005. Google Scholar
  20. Y. Emek and A. Rosén. Semi-streaming set cover. In Proc. 41st Int'l Colloq. Automata Lang. Prog. (ICALP), volume 8572 of Lect. Notes in Comp. Sci., pages 453-464, 2014. Google Scholar
  21. U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. Google Scholar
  22. N. Garg and J. Koenemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM Journal on Computing (SIAM), 37(2):630-652, 2007. Google Scholar
  23. T. Grossman and A. Wool. Computational experience with approximation algorithms for the set covering problem. Euro. J. Oper. Res., 101(1):81-92, 1997. Google Scholar
  24. S. Har-Peled, P. Indyk, S. Mahabadi, and A. Vakilian. Towards tight bounds for the streaming set cover problem. In Proc. 35th ACM Symp. on Principles of Database Systems (PODS), pages 371-383, 2016. Google Scholar
  25. N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Foundations of Computer Science, 1982. SFCS'08. 23rd Annual Symposium on, pages 312-320. IEEE, 1982. Google Scholar
  26. M. J. Kearns and U. V. Vazirani. An introduction to computational learning theory. MIT press, 1994. Google Scholar
  27. C. Koufogiannakis and N. E. Young. A nearly linear-time PTAS for explicit fractional packing and covering linear programs. Algorithmica, 70(4):648-674, 2014. Google Scholar
  28. Y. T. Lee and A. Sidford. Path finding methods for linear programming: Solving linear programs in O(vrank) iterations and faster algorithms for maximum flow. In Proc. 55th Annual IEEE Symp. Found. Comput. Sci. (FOCS), pages 424-433, 2014. Google Scholar
  29. C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM (JACM), 41(5):960-981, 1994. Google Scholar
  30. A. McGregor and H. T. Vu. Better streaming algorithms for the maximum coverage problem. In 20th International Conference on Database Theory, ICDT, pages 22:1-22:18, 2017. Google Scholar
  31. D. Moshkovitz. The projection games conjecture and the NP-hardness of ln n-approximating set-cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 276-287. Springer, 2012. Google Scholar
  32. S. A. Plotkin, D. B. Shmoys, and É. Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20(2):257-301, 1995. Google Scholar
  33. R. Raz and S. Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proc. 29th Annual ACM Symp. Theory Comput. (STOC), 1997. Google Scholar
  34. B. Saha and L. Getoor. On maximum coverage in the streaming model & application to multi-topic blog-watch. In Proc. SIAM Int. Conf. Data Mining (SDM), pages 697-708, 2009. Google Scholar
  35. D. Wang, S. Rao, and M. W. Mahoney. Unified acceleration method for packing and covering problems via diameter reduction. In Proc. 43st Int'l Colloq. Automata Lang. Prog. (ICALP), pages 50:1-50:13, 2016. Google Scholar
  36. N. E. Young. Randomized rounding without solving the linear program. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 170-178, 1995. Google Scholar
  37. N. E. Young. Nearly linear-work algorithms for mixed packing/covering and facility-location linear programs. arXiv preprint arXiv:1407.3015, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact