Greedy Matching: Guarantees and Limitations

Bert Besser, Matthias PoloczekAlgorithmica 2017 · DOI

TL;DR

This paper analyzes the performance of greedy algorithms for the maximum cardinality matching problem, a fundamental task in computer science with applications in various fields. The authors demonstrate that despite their simplicity and excellent empirical performance, greedy algorithms have inherent limitations and cannot achieve optimal or near-optimal solutions in all cases, even with randomization. They provide theoretical bounds and construct specific "hard" graphs that expose these limitations.

What Problem Does This Paper Address?

The maximum cardinality matching problem aims to find the largest possible set of edges in a graph such that no two edges share a vertex. Greedy algorithms, which iteratively pick an edge and remove its endpoints, are attractive due to their simplicity and efficiency. While randomized greedy algorithms like MINGREEDY have shown impressive performance on many graph types, their theoretical guarantees have been lacking. This paper addresses the question of how good these greedy algorithms can actually be, both in terms of worst-case performance and their fundamental limitations compared to more complex algorithms. Specifically, it investigates the approximation ratios achievable by greedy algorithms, especially when the maximum degree of the graph is bounded.

Methods

The authors employ a combination of theoretical analysis and constructive proofs. They introduce specific families of graphs designed to challenge greedy algorithms, demonstrating their worst-case performance. For analyzing the limitations of the greedy paradigm, they adopt the "priority algorithm" model, which formalizes the myopic decision-making process of greedy algorithms. This model allows them to establish inapproximability bounds for both deterministic and randomized priority algorithms. They also analyze specific variants of greedy algorithms like EDSM and MDS.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and constructs specific graph families as "hard instances" rather than using standard datasets.

Key Insights and Ideas

  • Greedy algorithms are surprisingly limited: Even sophisticated randomized greedy algorithms like MINGREEDY cannot achieve a constant approximation ratio on certain bipartite graphs. This highlights a fundamental gap between their empirical success and theoretical worst-case performance.
  • Degree matters: The maximum degree of a graph significantly impacts the performance guarantees of greedy algorithms. The paper provides better bounds for graphs with bounded maximum degrees.
  • Randomness isn't a silver bullet: While randomization can improve performance, it doesn't overcome the inherent limitations of the greedy approach. The paper shows that even randomized priority algorithms have significant inapproximability bounds.
  • The "priority algorithm" model is powerful: This model provides a formal framework to study the limitations of greedy algorithms by framing them as a game against an adversary.

Key Results

  • MINGREEDY's limitations: MINGREEDY (and its variants) cannot achieve an approximation ratio of $1/2 + \epsilon$ for any $\epsilon > 0$ on certain bipartite graphs, even with randomization.
  • Bounded degree guarantees: For graphs with maximum degree $\Delta$, MINGREEDY achieves an approximation ratio of $\frac{\Delta-1}{2\Delta-3}$ for $\Delta \ge 3$, and $\frac{2}{3}$ for $\Delta=3$. These bounds also hold for deterministic variants.
  • Inapproximability for priority algorithms:
    • Deterministic adaptive priority algorithms cannot achieve better than a $1/2$ approximation ratio in the vertex model.
  • Fully randomized priority algorithms cannot achieve better than a $1/2$ expected approximation ratio.
  • k-uniform hypergraphs: No greedy adaptive priority algorithm can achieve better than a $\frac{k-1}{k}$ approximation ratio for k-uniform hypergraph matching.

Limitations and Future Work

  • Conjecture on $\Delta$-regular graphs: The authors conjecture that MINGREEDY achieves an approximation ratio of $\frac{\Delta-1}{2\Delta-3}$ for all graphs with maximum degree $\Delta$, but only prove it for $\Delta=3$ and $\Delta$-regular graphs.
  • Exploiting random neighbor selection: The paper notes that the guarantee for MINGREEDY doesn't fully exploit the fact that picking a random neighbor has a good probability of being optimal, especially for small degrees. This is left as future work.
  • Comparison to other paradigms: The paper concludes that greedy-like algorithms cannot compete with algorithms based on augmenting paths or algebraic methods, suggesting further investigation into these more complex approaches.

Summary updated

BibTeX
@article{besser2017greedy,
  author = {Bert Besser and Matthias Poloczek},
  title = {{Greedy Matching: Guarantees and Limitations}},
  journal = {Algorithmica},
  year = {2017},
  doi = {10.1007/s00453-015-0062-2},
}
Figure