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

DOI10.1137/1.9781611973402.82zbMATH Open1421.68109arXiv1307.2696OpenAlexW2951973862MaRDI QIDQ5384044FDOQ5384044

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)

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.

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

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

zbMATH Keywords

maximum matchingprimal-dual methodscontinuous linear programmingoblivious algorithms

Mathematics Subject Classification ID

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

Cited In (6)

• Analyzing node-weighted oblivious matching problem via continuous LP with jump discontinuity
• Title not available (Why is that?)
• Ranking on arbitrary graphs: rematch via continuous linear programming
• Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching
• Greedy matching: guarantees and limitations
• Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals

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)