nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Engineering a Bipartite Matching Algorithm in the Semi-Streaming Model

verfasst von : Lasse Kliemann

Erschienen in: Algorithm Engineering

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We describe the Algorithm Engineering process for designing a pass-efficient semi-streaming algorithm for the bipartite maximum matching problem, using the augmenting paths technique. This algorithm was first published by the author at SEA 2011. This text not only discusses the algorithm, but also describes how Algorithm Engineering helped to invent and refine it.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Integrating Sequencing and Scheduling: A Generic Approach with Two Exemplary Industrial Applications

Nächstes Kapitel Engineering Art Galleries

This can also be achieved by orienting the edges

$$\begin{aligned} {\varvec{E}} :=\left\{ (a,b) \in A \times B; \{a,b\} \in E \setminus M\right\} \cup \left\{ (b,a) \in B \times A; \{a,b\} \in M \right\} \end{aligned}$$

and then using normal BFS in this directed bipartite graph $(A,B,{\varvec{E}})$.

By ${\text {poly}}x$ we denote a polynomial in x, another way to write $\mathcal {O}\left( {\text {poly}}x\right) $ is $x^{\mathcal {O}\left( 1\right) }$.

The “semi” attribute was chosen since the term “streaming model” is generally associated with logarithmic space. The semi-streaming model is considered “between” logarithmic and quadratic space, the latter being equivalent to the RAM model since a graph can be stored in $\mathcal {O}\left( n^2\right) $ bits of space.

The statement (i) can also be formulated as the algorithm with threshold 0 being a $(\lambda _1,\lambda _2,0)$ DAP approximation algorithm.

Recall that so far we have always used $\lambda _1=\lambda _2$. A distinction between the two parameters will be made shortly.

Ahn, K.J., Guha, S.: Linear programming in the semi-streaming model with application to the maximum matching problem. Inf. Comput. 222, 59–79 (2013). Conference version at ICALP 2011MathSciNetCrossRefMATH

Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58, 137–147 (1999). Conference version at STOC 1996MathSciNetCrossRefMATH

Alt, H., Blum, N., Mehlhorn, K., Paul, M.: Computing a maximum cardinality matching in a bipartite graph in time $O(n^{1.5}\sqrt{m/\log n})$. Inf. Process. Lett. 37, 237–240 (1991)MathSciNetCrossRefMATH

Assadi, S., Khanna, S., Li, Y., Yaroslavtsev, G.: Tight bounds for linear sketches of approximate matchings (2015). http://arxiv.org/abs/1505.01467

Berge, C.: Two theorems in graph theory. Proc. Natl. Acad. Sci. United States Am. 43(9), 842–844 (1957). http://www.pnas.org/content/43/9/842.short MathSciNetCrossRefMATH

Bury, M., Schwiegelshohn, C.: Sublinear estimation of weighted matchings in dynamic data streams. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 263–274. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48350-3_23 CrossRef

Cherkassky, B.V., Goldberg, A.V., Martin, P.: Augment or push: a computational study of bipartite matching and unit-capacity flow algorithms. ACM J. Exp. Algorithms 3, Article No. 8 (1998). http://www.jea.acm.org/1998/CherkasskyAugment/

Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M.T., Monemizadeh, M.: Brief announcement: new streaming algorithms for parameterized maximal matching and beyond. In: Proceedings of the 27th ACM Symposium on Parallel Algorithms and Architectures, Portland, Oregon, USA, June 2015 (SPAA 2015) (2015)

Chitnis, R., Cormode, G., Hajiaghayi, M.T., Monemizadeh, M.: Parameterized streaming: maximal matching and vertex cover. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, California, USA, January 2015 (SODA 2015) (2015)

10.

Crouch, M., Stubbs, D.M.: Improved streaming algorithms for weighted matching, via unweighted matching. In: Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and Randomization and Computation, Barcelona, Spain, September 2014 (APPROX RANDOM 2014) (2014)

11.

Eggert, S., Kliemann, L., Munstermann, P., Srivastav, A.: Bipartite matching in the semi-streaming model. Algorithmica 63, 490–508 (2012). Conference version at ESA 2009MathSciNetCrossRefMATH

12.

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

13.

Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theoret. Comput. Sci. 348, 207–217 (2005). Conference version at ICALP 2004MathSciNetCrossRefMATH

14.

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

15.

Flajolet, P., Martin, G.N.: Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31(2), 182–209 (1985)MathSciNetCrossRefMATH

16.

Guruswami, V., Onak, K.: Superlinear lower bounds for multipass graph processing. In: Electronic Colloquium on Computational Complexity (2013)

17.

Henzinger, M.R., Raghavan, P., Rajagopalan, S.: Computing on data streams. External Memory Algorithms. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 50, pp. 107–118 (2000)

18.

Hopcroft, J.E., Karp, R.M.: An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225–231 (1973)MathSciNetCrossRefMATH

19.

Kalyansundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math. 5, 545–557 (1992)MathSciNetCrossRefMATH

20.

Kapralov, M., Khanna, S., Sudan, M.: Approximating matching size from random streams. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, Portland, Oregon, USA, January 2014 (SODA 2014) (2014)

21.

Kliemann, L.: Matching in bipartite graph streams in a small number of passes. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 254–266. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20662-7_22 CrossRef

22.

Konrad, C.: Maximum matching in turnstile streams. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 840–852. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48350-3_70 CrossRef

23.

Konrad, C., Magniez, F., Mathieu, C.: Maximum matching in semi-streaming with few passes. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX/RANDOM -2012. LNCS, vol. 7408, pp. 231–242. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32512-0_20 CrossRef

24.

Kozen, D.C.: The Design and Analysis of Algorithms. Springer, Heidelberg (1992)CrossRefMATH

25.

Langguth, J., Manne, F., Sanders, P.: Heuristic initialization for bipartite matching problems. ACM J. Exp. Algorithmics 15, 1.3:1.1–1.3:1.22 (2010). http://doi.acm.org/10.1145/1712655.1712656 MathSciNetMATH

26.

McGregor, A.: Finding graph matchings in data streams. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX/RANDOM -2005. LNCS, vol. 3624, pp. 170–181. Springer, Heidelberg (2005). doi:10.1007/11538462_15 CrossRef

27.

Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, (FOCS 2004), pp. 248–255 (2004). http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.40, http://www.mimuw.edu.pl/ mucha/pub/mucha_sankowski_focs04.pdf

28.

Munro, J.I., Paterson, M.: Selection and sorting with limited storage. Theoret. Comput. Sci. 12, 315–323 (1980). Conference version at FOCS 1978MathSciNetCrossRefMATH

29.

Muthukrishnan, M.: Data streams: algorithms and applications. Found. Trends Theoret. Comput. Sci. 1(2), 1–67 (2005). http://algo.research.googlepages.com/eight.ps MathSciNetCrossRefMATH

30.

Setubal, J.C.: Sequential and parallel experimental results with bipartite matching algorithms. Technical report IC-96-09, Institute of Computing, University of Campinas, Brazil (1996). http://www.dcc.unicamp.br/ic-tr-ftp/1996/96-09.ps.gz

31.

Zelke, M.: Algorithms for streaming graphs. Ph.D. thesis, Mathematisch-Naturwissenschaftliche Fakultät II, Humboldt-Universität zu Berlin (2009). http://www.tks.informatik.uni-frankfurt.de/getpdf?id=561

Titel: Engineering a Bipartite Matching Algorithm in the Semi-Streaming Model
verfasst von: Lasse Kliemann
Verlag: Springer International Publishing
Buch: Algorithm Engineering
Print ISBN: 978-3-319-49486-9

Electronic ISBN: 978-3-319-49487-6

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-49487-6_11

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"