Document Open Access Logo

Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching

Authors Michael Crouch, Daniel M. Stubbs

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.96.pdf
  • Filesize: 403 kB
  • 9 pages

Document Identifiers

Author Details

Michael Crouch
Daniel M. Stubbs

Cite As Get BibTex

Michael Crouch and Daniel M. Stubbs. Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 96-104, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.96

Abstract

We present a (4 + epsilon) approximation algorithm for weighted graph matching which applies in the semistreaming, sliding window, and MapReduce models; this single algorithm improves the previous best algorithm in each model. The algorithm operates by reducing the maximum-weight matching problem to a polylog number of copies of the maximum-cardinality matching problem. The algorithm also extends to provide approximation guarantees for the more general problem of finding weighted independent sets in p-systems (which include intersections of p matroids and p-bounded hypergraph matching).

Subject Classification

Keywords
  • Streaming Algorithms
  • Graph Matching
  • Weighted Graph Matching
  • MapReduce
  • Independence Systems

Metrics

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

References

  1. Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Streaming algorithms via precision sampling. FOCS, 2011. Google Scholar
  2. B.V. Ashwinkumar. Buyback problem - approximate matroid intersection with cancellation costs. In ICALP, pages 379-390, 2011. Google Scholar
  3. Ajesh Babu, Nutan Limaye, J Radhakrishnan, and Girish Varma. Streaming algorithms for language recognition problems. Theoretical Computer Science, 494:13-23, 2013. Google Scholar
  4. Ziv Bar-Yossef, Ravi Kumar, and D Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In SODA, pages 623-632, January 2002. Google Scholar
  5. Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: Matchings, matroids, and more. IPCO, 2014. To appear. Google Scholar
  6. Michael Crouch, Andrew McGregor, and Daniel Stubbs. Dynamic graphs in the sliding-window model. ESA, 2013. Google Scholar
  7. Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM Journal on Computing, 31(6):1794, 2002. Google Scholar
  8. Leah Epstein, Asaf Levin, Julián Mestre, and Danny Segev. Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM Journal on Discrete Mathematics, 25(3):1251-1265, January 2011. Google Scholar
  9. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science, 348(2-3):207-216, December 2005. Google Scholar
  10. Piotr Indyk and David P Woodruff. Optimal approximations of the frequency moments of data streams. In STOC, pages 202-208. ACM, 2005. Google Scholar
  11. Thomas A Jenkyns. The efficacy of the “greedy” algorithm. Proceedings of the 7th Southeastern Conference on Combinatorics, Graph Theory and Computing, pages 341-350, 1976. Google Scholar
  12. Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In SODA, pages 938-948, 2010. Google Scholar
  13. Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in MapReduce. In SPAA, New York, New York, USA, 2011. ACM Press. Google Scholar
  14. Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. Recognizing well-parenthesized expressions in the streaming model. In STOC, pages 261-270. ACM, 2010. Google Scholar
  15. Andrew McGregor. Finding graph matchings in data streams. APPROX-RANDOM, 2005. Google Scholar
  16. Silvio Micali and Vijay V. Vazirani. An O(sqrt(|V|) |E|) algorithm for finding maximum matching in general graphs. In FOCS, pages 17-27, 1980. Google Scholar
  17. Mariano Zelke. Weighted matching in the semi-streaming model. Algorithmica, pages 669-680, 2012. 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