Greedy Matching: Guarantees and Limitations
详细信息 查看全文
- 作者：Bert Besser ; Matthias Poloczek
- 关键词：Maximum matching ; Greedy algorithms ; Approximation algorithms ; Priority algorithms ; Randomized algorithms
- 刊名：Algorithmica
- 出版年：2017
- 出版时间：January 2017
- 年：2017
- 卷：77
- 期：1
- 页码：201-234
- 全文大小：
- 刊物类别：Computer Science
- 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
- 出版者：Springer US
- ISSN：1432-0541
- 卷排序：77
文摘
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.