Abstract
Since Tinhofer proposed the MinGreedy algorithm for maximum cardinality matching in 1984, several experimental studies found the randomized algorithm to perform excellently for various classes of random graphs and benchmark instances. In contrast, only few analytical results are known. We show that MinGreedy cannot improve on the trivial approximation ratio of \(\frac{1}{2}\) whp., even for bipartite graphs. Our hard inputs seem to require a small number of high-degree nodes. This motivates an investigation of greedy algorithms on graphs with maximum degree \(\varDelta \): we show that MinGreedy achieves a \({\frac{{\varDelta }-1}{2{\varDelta }-3}} \)-approximation for graphs with \({\varDelta } {=} 3\) and for \(\varDelta \)-regular graphs, and a guarantee of \({\frac{{\varDelta }-1/2}{2{\varDelta }-2}} \) for graphs with maximum degree \({\varDelta } \). Interestingly, our bounds even hold for the deterministic MinGreedy that breaks all ties arbitrarily. Moreover, we investigate the limitations of the greedy paradigm, using the model of priority algorithms introduced by Borodin, Nielsen, and Rackoff. We study deterministic priority algorithms and prove a \({\frac{{\varDelta }-1}{2{\varDelta }-3}}\)-inapproximability result for graphs with maximum degree \({\varDelta } \); thus, these greedy algorithms do not achieve a \(\frac{1}{2} {+} \varepsilon \)-approximation and in particular the \(\frac{2}{3}\)-approximation obtained by the deterministic MinGreedy for \({\varDelta } {=} 3\) is optimal in this class. For k-uniform hypergraphs we show a tight \(\frac{1}{k}\)-inapproximability bound. We also study fully randomized priority algorithms and give a \(\frac{5}{6}\)-inapproximability bound. Thus, they cannot compete with matching algorithms of other paradigms.
Similar content being viewed by others
References
Angelopoulos, S., Borodin, A.: Randomized priority algorithms. Theor. Comput. Sci. 411(26–28), 2542–2558 (2010)
Aronson, J., Dyer, M.E., Frieze, A.M., Suen, S.: Randomized greedy matching II. Random Struct. Algorithms 6(1), 55–74 (1995)
Aronson, J., Frieze, A.M., Pittel, B.: Maximum matchings in sparse random graphs: Karp–Sipser revisited. Random Struct. Algorithms 12(2), 111–177 (1998)
Bennett, P., Bohman, T.: A Natural Barrier in Random Greedy Hypergraph Matching. CoRR (2012).arXiv:1210.3581
Berger, B., Singh, R., Xu, J.: Graph algorithms for biological systems analysis. In: Proceedings of the Nineteenth Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 142–151 (2008)
Besser, B., Werth, B.: On the Approximation Performance of Degree Heuristics for Matching. CoRR (2015).arXiv:1504.05830
Borodin, A., Boyar, J., Larsen, K.S., Mirmohammadi, N.: Priority algorithms for graph optimization problems. Theor. Comput. Sci. 411(1), 239–258 (2010)
Borodin, A., Ivan, I., Ye, Y., Zimny, B.: On sum coloring and sum multi-coloring for restricted families of graphs. Theor. Comput. Sci. 418, 1–13 (2012)
Borodin, A., Nielsen, M.N., Rackoff, C.: (Incremental) priority algorithms. Algorithmica 37(4), 295–326 (2003)
Chan, T.H.H., Chen, F., Wu, X., Zhao, Z.: Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints. In: Proceedings of the Twenty-Fifth Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 1112–1122 (2014)
Chan, Y., Lau, L.: On linear and semidefinite programming relaxations for hypergraph matching. Math. Program. 135(1–2), 123–148 (2012)
Cheng, Y.Q., Wu, V., Collins, R.T., Hanson, A.R., Riseman, E.M.: Maximum-weight bipartite matching technique and its application in image feature matching. In: Proceedings of the SPIE Visual Communications and Image Processing (1996)
Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In: Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 509–518 (2013)
Davis, S., Impagliazzo, R.: Models of greedy algorithms for graph problems. Algorithmica 54(3), 269–317 (2009)
Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)
Dyer, M.E., Frieze, A.M.: Randomized greedy matching. Random Struct. Algorithms 2(1), 29–46 (1991)
Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449–467 (1965)
Edmonds, J., Fulkerson, D.R.: Transversals and matroid partition. J. Res. Natl. Bur. Stand 69B(3), 147–153 (1965)
Frieze, A.M., Radcliffe, A.J., Suen, S.: Analysis of a simple greedy matching algorithm on random cubic graphs. Comb. Probab. Comput. 4, 47–66 (1995)
Gabow, H.N.: An efficient implementation of Edmonds’ algorithm for maximum matching on graphs. J. ACM 23(2), 221–234 (1976)
Gabow, H.N.: Set-Merging for the Matching Algorithm of Micali and Vazirani. CoRR (2014). arXiv:1501.00212
Geelen, J.F.: An algebraic matching algorithm. Combinatorica 20(1), 61–70 (2000)
Goel, G., Tripathi, P.: Matching with our eyes closed. In: Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 718–727 (2012)
Goldberg, A.V., Karzanov, A.V.: Maximum skew-symmetric flows and matchings. Math. Program. 100(3), 537–568 (2004)
Harvey, N.J.A.: Algebraic algorithms for matching and matroid problems. SIAM J. Comput. 39(2), 679–702 (2009)
Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15(1), 20–39 (2006)
Hosaagrahara, M., Sethu, H.: Degree-sequenced matching algorithms for input-queued switches. Telecommun. Syst. 34(1–2), 37–49 (2007)
Hougardy, S.: Linear time approximation algorithms for degree constrained subgraph problems. In: Cook, W., Lovász, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 185–200 (2009)
Huang, N., Borodin, A.: Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization. In: Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC), pp. 528–539 (2014)
Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. 2(1), 68–72 (1989)
Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pp. 587–596 (2011)
Karp, R.M., Sipser, M.: Maximum matchings in sparse random graphs. In: Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 364–375 (1981)
Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 352–358 (1990)
Korte, B., Hausmann, D.: An analysis of the greedy algorithm for independence systems. Ann. Discrete Math. 2, 65–74 (1978)
Lovász, L., Plummer, M.D.: Matching Theory. North-Holland, Amsterdam (1986)
Magun, J.: Greedy matching algorithms: an experimental study. ACM J. Exp. Algorithmics 3, 6 (1998)
Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pp. 597–606 (2011)
Miller, Z., Pritikin, D.: On randomized greedy matchings. Random Struct. Algorithms 10(3), 353–383 (1997)
Mucha, M., Sankowski, P.: Maximum matchings via gaussian elimination. In: Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 248–255 (2004)
Poloczek, M.: Bounds on greedy algorithms for MAX SAT. In: Proceedings of the 19th Annual European Symposium on Algorithms (ESA), pp. 37–48 (2011)
Poloczek, M., Szegedy, M.: Randomized greedy algorithms for the maximum matching problem with new analysis. In: Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 708–717 (2012)
Roth, A.E., Sönmez, T., Ünver, M.U.: Pairwise kidney exchange. J. Econ. Theory 125(2), 151–188 (2005)
Tinhofer, G.: A probabilistic analysis of some greedy cardinality matching algorithms. Ann. Oper. Res. 1, 239–254 (1984)
Tripathi, P.: Allocation Problems with Partial Information. Ph.D. thesis, Georgia Institute of Technology (2012)
Vazirani, V.V.: A Simplification of the MV Matching Algorithm and Its Proof. CoRR (2013).arXiv:1210.4594
Yao, A.C.C.: Lower bounds by probabilistic arguments. In: Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), pp. 420–428. IEEE (1983)
Acknowledgments
The authors would like to thank Georg Schnitger for many helpful discussions, and Allan Borodin and Nicolas Peña for their valuable comments on an early draft of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
B. Besser: Partially supported by DFG SCHN 503/6-1.
M. Poloczek: Supported by the Alexander von Humboldt Foundation within the Feodor Lynen program, and in part by NSF Grant CCF-1115256.
An erratum to this article is available at http://dx.doi.org/10.1007/s00453-017-0281-9.
Appendix: A Linear Time Implementation of MinGreedy
Appendix: A Linear Time Implementation of MinGreedy
For MRG and Ranking Poloczek and Szegedy [41] propose a data structure that allows to run both algorithms in linear time. Greedy can also be implemented in linear time using a data structure similar to the one we describe below.
Given an adjacency list representation of the input graph \(G = (V=\{0,\ldots ,n-1\},E)\), the data structure can be initialized in linear time \(O(|E| + |V|)\). At any time during MinGreedy, the data structure supports each of the following operations in constant time: selection of a random node of minimum (non-zero) degree, selection of a random neighbor of a given node, and the deletion of a given edge. Hence MinGreedy can be implemented in linear time since a minimum degree node and a neighbor are selected at most \(\frac{|V|}{2}\) times and each of the |E| edges is removed exactly once.
How is a minimum degree node u selected in constant time? Consider a step of MinGreedy and let \( d_0<d_1<\cdots <d_k \) be the different degrees currently present in the graph, where \( d_0=0 \) is the degree of already isolated nodes. We use an array S which is partitioned into sub-arrays \( S_i \) (\( 0\le i\le k \)) such that \(S_i\) precedes all \(S_j\) with \(i < j\). Each \(S_i\) contains all nodes that currently have degree \( d_i \) in contiguous cells of S . A doubly linked list D stores (from head to tail) the borders of \( S_0,S_1,\ldots ,S_k \). Node u is selected by reading the second entry in D , which stores nodes of minimum degree \( d_1 \), and choosing a random cell in \( S_1 \).
To select a random neighbor v of u in constant time, instead of adjacency lists we utilize adjacency arrays (which have same lengths as the lists and can be computed in linear time during the preprocessing phase). To pick v from the adjacency array \( A_u \) of u , we assert that the currently available neighbors of u are stored in a consecutive part of \( A_u \).
Now that nodes u and v are selected, the edge (u, v), and all incident edges of u and v are removed from the data structure. We remove these edges one-by-one, each in constant time.
This is how we update the adjacency arrays. Let a node x and an index of a cell in \( A_x \) be given, say containing neighbor y . Assume that the array cell in \( A_x \) containing node y also stores the index of the array cell in \( A_y \) containing node x as a reference and vice versa. In order to remove the edge (x, y) , we move the entry of the last non-empty cell in \(A_x\) to the position of y , and handle \(A_y \) and x analogously. We also update the references of the two moved entries accordingly; this is done in constant time using the references stored inside the moved entries. The references are initialized during the construction of the adjacency arrays.
How to update S and D for the removal of an edge (x, y) ? Since the degrees \( d_x,d_y \) of x respectively y are decreased by exactly one, these nodes are moved from sub-array \( S_{d_x} \) to sub-array \( S_{d_x-1} \) respectively from \( S_{d_y} \) to \( S_{d_y-1} \). We proceed analogously for x and y . To move x to its new sub-array, we utilize two helper arrays \( P_D,P_S \): \( P_D[x]\) stores a pointer to the D -entry containing x , \( P_S[x] \) holds the index of the cell in S containing x . The entry of node x in the sub-array \( S_{d_x} \) is replaced by the “leftmost” node in \( S_{d_x} \), i.e., the node stored at the smallest index, and x is appended to the “right” of \( S_{d_x-1} \). If \( S_{d_x} \) is now empty, we remove it from D in constant time using the pointer \( P_D[x] \). If \( S_{d_x-1} \) does not yet exist, i.e., x is now the only node of degree \( d_x-1 \), then we create \( S_{d_x-1} \) at the now cleared position in S and insert \( S_{d_x-1} \) before \( S_{d_x} \) (or before the successor of \( S_{d_x} \), if \( S_{d_x} \) was removed), also in constant time. The pointers in \( P_D \) and the addresses stored in \( P_S \) are updated accordingly.
Note that \( S,D,P_S,P_D \) can be initialized in time \( O(|E|+|V|) \) during the preprocessing phase by scanning through the adjacency lists of G a constant number of times.
Rights and permissions
About this article
Cite this article
Besser, B., Poloczek, M. Greedy Matching: Guarantees and Limitations. Algorithmica 77, 201–234 (2017). https://doi.org/10.1007/s00453-015-0062-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-015-0062-2