Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints

T.-h. Hubert Chan, Fei Chen, Xiaowei Wu, Zhichao Zhao

Abstract

The Ranking algorithm is a cornerstone of randomized greedy matching, yet its performance on arbitrary (non-bipartite) graphs has remained theoretically elusive for decades. While it is well-known that any greedy algorithm achieves a performance ratio of 0.5, previous attempts to prove a significantly higher ratio for Ranking on arbitrary graphs have met with limited success or non-reproducible results. In this work, we revisit the Ranking algorithm using a Factor-Revealing Linear Programming (LP) framework. By transitioning to a continuous LP relaxation and introducing a novel "boundary" constraint, we prove a new theoretical lower bound of $\frac{2(5-\sqrt{7})}{9} \approx 0.523$. This result represents the best known theoretical guarantee to date and provides a robust framework for analyzing greedy algorithms in functional spaces.

Introduction

The maximum matching problem—finding the largest set of edges without common vertices—is a fundamental problem in combinatorial optimization with direct applications in online advertising and exchange markets. In many real-world scenarios, the underlying graph is unknown or arrives online, necessitating the use of greedy algorithms.

A simple greedy approach, which matches nodes as they are encountered, is guaranteed to find a matching at least half the size of the maximum matching (a ratio of 0.5). The Ranking algorithm, introduced by Karp, Vazirani, and Vazirani, improves this by picking a random permutation of nodes to determine the probing order. While Ranking is known to achieve a ratio of $1 - 1/e \approx 0.653$ on bipartite graphs, its performance on arbitrary graphs has been much harder to characterize. For nearly twenty years, the best theoretical proof only marginally exceeded the 0.5 baseline. This paper bridges that gap by providing a new analytical framework that pushes the lower bound to 0.523.

Methodology: The Factor-Revealing LP

To analyze the performance of Ranking, we employ a "Factor-Revealing LP" approach. This method models the algorithm's behavior as a set of linear constraints, where the objective is to minimize the performance ratio.

From Discrete to Continuous

Traditional analysis often relies on discrete LPs for a fixed number of nodes $n$. However, as $n$ grows, these LPs become computationally expensive and difficult to solve analytically. We address this by moving to a continuous LP relaxation. In this regime, variables are treated as functions over the interval $[0, 1]$, and discrete sums are replaced by integrals. This allows us to analyze the limiting behavior of the algorithm as the graph size approaches infinity.

Structural Constraints

The success of our LP depends on three categories of constraints derived from the structural properties of the Ranking algorithm:

  1. Monotone Constraints: These ensure that the probability of a node being matched does not increase as its rank in the random permutation grows.
  2. Evolving Constraints: These describe the relationship between the matching probabilities of different nodes based on their relative ranks.
  3. Boundary Constraints: This is the most critical addition. We derived a sophisticated set of relations that describe the behavior of the algorithm at the "edges" of the ranking process. Our analysis demonstrates that without these boundary conditions, the LP framework is mathematically incapable of proving a ratio better than 0.5.

Solving the Continuous LP

Solving a continuous LP requires more than standard simplex methods. We developed new duality and complementary slackness characterizations specifically designed for functional spaces. By constructing a dual solution that satisfies the monotone and boundary conditions, we were able to derive a closed-form analytical solution for the lower bound.

Experimental Validation and Upper Bounds

While our primary focus is theoretical, we conducted numerical experiments to guide our derivations and test the limits of the Ranking algorithm.

Correcting Previous Claims

In 2012, Goel and Tripathi suggested an experimental ratio of 0.56 for Ranking. However, our attempts to reproduce these results revealed a discrepancy. As the number of nodes $n$ in the experimental model increased, the ratio dropped significantly, eventually approaching 0.5001. This suggests that previous experimental estimates were likely artifacts of small graph sizes rather than true asymptotic bounds.

The Double Bomb Graph

To find an upper bound on Ranking's performance, we tested the algorithm against a synthetic hard instance known as the "Double Bomb Graph." This graph structure is specifically designed to defeat greedy matching strategies. Our experiments on this graph suggest that the Ranking algorithm cannot achieve a performance ratio better than 0.724 in general.

Conclusion

This paper establishes a new theoretical benchmark for the Ranking algorithm on arbitrary graphs, proving a performance ratio of at least 0.523. Beyond the specific numerical improvement, our work contributes a generalized primal-dual framework for continuous LPs. This framework provides a powerful tool for future researchers to analyze complex randomized algorithms where discrete analysis proves insufficient. While a gap remains between our lower bound (0.523) and the experimental upper bound (0.724), the introduction of boundary constraints marks a significant step toward a complete understanding of greedy matching on arbitrary graphs.

Summary updated

Abstract

Motivated by online advertisement and exchange settings, greedy randomized algorithms for the maximum matching problem have been studied, in which the algorithm makes (random) decisions that are essentially oblivious to the input graph. Any greedy algorithm can achieve performance ratio 0.5, which is the expected number of matched nodes to the number of nodes in a maximum matching. Since Aronson, Dyer, Frieze and Suen proved that the Modified Randomized Greedy (MRG) algorithm achieves performance ratio 0.5 + \epsilon (where \epsilon = frac{1}{400000}) on arbitrary graphs in the mid-nineties, no further attempts in the literature have been made to improve this theoretical ratio for arbitrary graphs until two papers were published in FOCS 2012. Poloczek and Szegedy also analyzed the MRG algorithm to give ratio 0.5039, while Goel and Tripathi used experimental techniques to analyze the Ranking algorithm to give ratio 0.56. However, we could not reproduce the experimental results of Goel and Tripathi. In this paper, we revisit the Ranking algorithm using the LP framework. Special care is given to analyze the structural properties of the Ranking algorithm in order to derive the LP constraints, of which one known as the \emph{boundary} constraint requires totally new analysis and is crucial to the success of our LP. We use continuous LP relaxation to analyze the limiting behavior as the finite LP grows. Of particular interest are new duality and complementary slackness characterizations that can handle the monotone and the boundary constraints in continuous LP. We believe our work achieves the currently best theoretical performance ratio of \frac{2(5-\sqrt{7})}{9} \approx 0.523 on arbitrary graphs. Moreover, experiments suggest that Ranking cannot perform better than 0.724 in general.
BibTeX
@inproceedings{chan2014ranking,
  author = {T.-H. Hubert Chan and Fei Chen and Xiaowei Wu and Zhichao Zhao},
  title = {{Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints}},
  booktitle = {SODA},
  year = {2014},
  doi = {10.1137/1.9781611973402.82},
}
Figure