Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints

DOI10.1137/1.9781611973402.82MaRDI QIDQ5384044zbMATH OpenOpenAlexFDO

Authors

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.2696

zbMATH Keywords

continuous linear programmingmaximum matchingoblivious algorithmsprimal-dual methods

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Programming involving graphs or networks (90C35)

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.

Recommendations

• Ranking on arbitrary graphs: rematch via continuous linear programming
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Tighter bounds for online bipartite matching
• Randomized primal-dual analysis of RANKING for online bipartite matching
• Analyzing node-weighted oblivious matching problem via continuous LP with jump discontinuity

Cited in

(7)

• Analyzing node-weighted oblivious matching problem via continuous LP with jump discontinuity
• Ranking on arbitrary graphs: rematch via continuous linear programming
• Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals
• scientific article; zbMATH DE number 7376006 (Why is no real title available?)
• Greedy matching: guarantees and limitations
• Matroid and knapsack house allocation
• Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching

This page was built for publication: Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384044)