More Web Proxy on the site http://driver.im/

research-article

Approximating Semi-matchings in Streaming and in Two-Party Communication

Authors:

Christian Konrad,

Adi RosénAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 12, Issue 3

Article No.: 32, Pages 1 - 21

https://doi.org/10.1145/2898960

Published: 25 April 2016 Publication History

Abstract

We study the streaming complexity and communication complexity of approximating unweighted semi-matchings. A semi-matching in a bipartite graph G = (A, B, E) with n = |A| is a subset of edges S⊆E that matches all A vertices to B vertices with the goal usually being to do this as fairly as possible. While the term semi-matching was coined in 2003 by Harvey et al. [2003], the problem had already previously been studied in the scheduling literature under different names.

We present a deterministic one-pass streaming algorithm that for any 0 ⩽ ϵ ⩽ 1 uses space Õ(n^1+ϵ and computes an O(n^(1−ϵ)/2)-approximation to the semi-matching problem. Furthermore, with O(log n) passes it is possible to compute an O(log n)-approximation with space Õ(n).

In the one-way two-party communication setting, we show that for every ϵ > 0, deterministic communication protocols for computing an O(n^1/(1+ϵ)c+1)-approximation require a message of size more than cn bits. We present two deterministic protocols communicating n and 2n edges that compute an O√n and an O(n^1/3)-approximation, respectively.

Finally, we improve on the results of Harvey et al. [2003] and prove new links between semi-matchings and matchings. While it was known that an optimal semi-matching contains a maximum matching, we show that there is a hierarchical decomposition of an optimal semi-matching into maximum matchings. A similar result holds for semi-matchings that do not admit length-two degree-minimizing paths.

References

[1]

D. Abraham. 2003. Algorithmics of Two-Sided Matching Problems. Master’s thesis. University of Glasgow.

[2]

K. J. Ahn and S. Guha. 2013. Linear programming in the semi-streaming model with application to the maximum matching problem. Inf. Comput. 222 (Jan. 2013), 59--79.

Digital Library

[3]

K. J. Ahn and S. Guha. 2014. Near linear time approximation schemes for uncapacitated and capacitated b-matching problems in nonbipartite graphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014). 239--258.

Digital Library

[4]

Y. Azar, J. S. Naor, and R. Rom. 1995. The competitiveness of on-line assignments. J. Algorithms 18, 2 (March 1995), 221--237.

Digital Library

[5]

C. Berge. 1957. Two theorems in graph theory. Proc. Natl. Acad. Sci. U. S. A. 43, 9 (1957), 842--844.

[6]

J. Bruno, E. G. Coffman, Jr., and R. Sethi. 1974. Scheduling independent tasks to reduce mean finishing time. Commun. ACM 17, 7 (July 1974), 382--387.

Digital Library

[7]

M. Crouch and D. M. Stubbs. 2014. 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)), Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore (Eds.), Vol. 28. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 96--104.

[8]

M. S. Crouch, A. McGregor, and D. Stubbs. 2013. Dynamic graphs in the sliding-window model. In Algorithms ESA 2013, Hans L. Bodlaender and Giuseppe F. Italiano (Eds.). Lecture Notes in Computer Science, Vol. 8125. Springer, Berlin, 337--348.

[9]

A. Czygrinow, M. Hanćkowiak, E. Szymańska, and W. Wawrzyniak. 2012. Distributed 2-approximation algorithm for the semi-matching problem. In Proceedings of the 26th International Conference on Distributed Computing (DISC’12). Springer-Verlag, Berlin, 210--222.

Digital Library

[10]

H. Esfandiari, M. T. Hajiaghayi, V. Liaghat, M. Monemizadeh, and K. Onak. 2015. Streaming algorithms for estimating the matching size in planar graphs and beyond. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). SIAM, 1217--1233.

Digital Library

[11]

J. Fakcharoenphol, B. Laekhanukit, and D. Nanongkai. 2014. Faster algorithms for semi-matching problems. ACM Trans. Algorithms 10, 3, Article 14 (May 2014), 23 pages.

Digital Library

[12]

J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. 2008. Graph distances in the data-stream model. SIAM J. Comput. 38, 5 (Dec. 2008), 1709--1727.

Digital Library

[13]

F. Galčík, J. Katrenič, and G. Semanišin. 2011. On computing an optimal semi-matching. In Proceedings of the 37th International Conference on Graph-Theoretic Concepts in Computer Science (WG’11). Springer-Verlag, Berlin, 250--261.

Digital Library

[14]

A. Goel, M. Kapralov, and S. Khanna. 2012. On the communication and streaming complexity of maximum bipartite matching. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 18.

Digital Library

[15]

V. Guruswami and K. Onak. 2013. Superlinear lower bounds for multipass graph processing. In Proceedings of the 28th Conference on Computational Complexity (CCC 2013). 287--298.

[16]

N. J. A. Harvey, R. E. Ladner, L. Lovász, and T. Tamir. 2003. Semi-matchings for bipartite graphs and load balancing. In Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS'03), F. Dehne, Jörg-Rödiger Sack, and M. Smid (Eds.). Springer Berlin Heidelberg, Ottawa, Ontario, Canada, 294--306. http://dx.doi.org/10.1007/978-3-540-45078-8_26.

[17]

W. A. Horn. 1973. Minimizing average flow time with parallel machines. Oper. Res. (1973), 846--847.

Digital Library

[18]

M. Kapralov. 2013. Better bounds for matchings in the streaming model. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’13).

Digital Library

[19]

M. Kapralov, S. Khanna, and M. Sudan. 2014a. Approximating matching size from random streams. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 734--751.

Digital Library

[20]

M. Kapralov, Y. T. Lee, C. Musco, C. Musco, and A. Sidford. 2014b. Single pass spectral sparsification in dynamic streams. In 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2014). 561--570.

Digital Library

[21]

J. Kleinberg, Y. Rabani, and É. Tardos. 2001. Fairness in routing and load balancing. J. Comput. Syst. Sci. 63, 1 (2001), 2--20.

Digital Library

[22]

C. Konrad, F. Magniez, and C. Mathieu. 2012. Maximum matching in semi-streaming with few passes. In Proceedings of 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems.

[23]

C. Konrad and A. Rosén. 2013. Approximating semi-matchings in streaming and in two-party communication. In Proceedings of the 40th International Conference on Automata, Languages, and Programming—Volume Part I (ICALP’13). Springer-Verlag, Berlin, 637--649.

Digital Library

[24]

Y. Lin and W. Li. 2004. Parallel machine scheduling of machine-dependent jobs with unit-length. Eur. J. Oper. Res. 156, 1 (July 2004), 261--266.

[25]

A. McGregor. 2014. Graph stream algorithms: A survey. SIGMOD Rec. 43, 1 (2014), 12.

Digital Library

Cited By

JIANG XHASHIMA SHATANO KTAKIMOTO E(2024)Online Job Scheduling with K ServersIEICE Transactions on Information and Systems10.1587/transinf.2023FCP0005E107.D:3(286-293)Online publication date: 1-Mar-2024
https://doi.org/10.1587/transinf.2023FCP0005
Dark JKonrad CAceto L(2020)Optimal lower bounds for matching and vertex cover in dynamic graph streamsProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.30(1-14)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.30

Approximating Semi-matchings in Streaming and in Two-Party Communication
1. Theory of computation

Recommendations

Approximating semi-matchings in streaming and in two-party communication
ICALP'13: Proceedings of the 40th international conference on Automata, Languages, and Programming - Volume Part I

We study the communication complexity and streaming complexity of approximating unweighted semi-matchings. A semi-matching in a bipartite graph G=(A, B, E), with n=|A|, is a subset of edges S⊆E that matches all A vertices to B vertices with the goal ...
Turnstile streaming algorithms might as well be linear sketches
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

In the turnstile model of data streams, an underlying vector x ∈ {--m,--m+1,..., m--1,m}ⁿ is presented as a long sequence of positive and negative integer updates to its coordinates. A randomized algorithm seeks to approximate a function f(x) with ...
Streaming algorithms for language recognition problems

We study the complexity of the following problems in the streaming model. Membership testing forDLIN. We show that every language in DLIN can be recognized by a randomized one-pass O(logn) space algorithm with an inverse polynomial one-sided error and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 12, Issue 3

June 2016

408 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/2930058

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 April 2016

Accepted: 01 October 2015

Revised: 01 July 2015

Received: 01 December 2013

Published in TALG Volume 12, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Icelandic Research Fund
ANR project RDAM

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
140
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

JIANG XHASHIMA SHATANO KTAKIMOTO E(2024)Online Job Scheduling with K ServersIEICE Transactions on Information and Systems10.1587/transinf.2023FCP0005E107.D:3(286-293)Online publication date: 1-Mar-2024
https://doi.org/10.1587/transinf.2023FCP0005
Dark JKonrad CAceto L(2020)Optimal lower bounds for matching and vertex cover in dynamic graph streamsProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.30(1-14)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.30

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents