File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/140984051
- Scopus: eid_2-s2.0-85053598931
- WOS: WOS:000443195600009
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming
Title | Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming |
---|---|
Authors | |
Keywords | oblivious matching problem continuous linear programming ranking algorithm |
Issue Date | 2018 |
Publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP |
Citation | SIAM Journal on Computing, 2018, v. 47 n. 4, p. 1529-1546 How to Cite? |
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 a performance ratio of 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 [Random Structures Algorithm, 6 (1991), pp. 29--46] proved that the modified randomized greedy algorithm achieves a performance ratio of $0.5 + epsilon$ (where $epsilon = frac{1}{400000}$) on arbitrary graphs in the midnineties, 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 [G. Goel and P. Tripathi, IEEE Computer Society, Los Alamitos, CA, 2012, pp. 718--727; M. Poloczek and M. Szegedy, IEEE Computer Society, Los Alamitos, CA, 2012, pp. 708--717]. In this paper, we revisit the ranking algorithm using the linear programming framework. Special care is given to analyze the structural properties of the ranking algorithm in order to derive the linear programming constraints, of which one known as the boundary constraint requires totally new analysis and is crucial to the success of our linear program (LP). We use continuous linear programming 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 linear programming. Improving previous work, this paper achieves a theoretical performance ratio of $frac{2(5-sqrt{7})}{9} approx 0.523$ on arbitrary graphs.
Read More: https://epubs.siam.org/doi/10.1137/140984051 |
Persistent Identifier | http://hdl.handle.net/10722/290735 |
ISSN | 2023 Impact Factor: 1.2 2023 SCImago Journal Rankings: 2.143 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, THH | - |
dc.contributor.author | CHEN, F | - |
dc.contributor.author | WU, X | - |
dc.contributor.author | ZHAO, Z | - |
dc.date.accessioned | 2020-11-02T05:46:22Z | - |
dc.date.available | 2020-11-02T05:46:22Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | SIAM Journal on Computing, 2018, v. 47 n. 4, p. 1529-1546 | - |
dc.identifier.issn | 0097-5397 | - |
dc.identifier.uri | http://hdl.handle.net/10722/290735 | - |
dc.description.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 a performance ratio of 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 [Random Structures Algorithm, 6 (1991), pp. 29--46] proved that the modified randomized greedy algorithm achieves a performance ratio of $0.5 + epsilon$ (where $epsilon = frac{1}{400000}$) on arbitrary graphs in the midnineties, 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 [G. Goel and P. Tripathi, IEEE Computer Society, Los Alamitos, CA, 2012, pp. 718--727; M. Poloczek and M. Szegedy, IEEE Computer Society, Los Alamitos, CA, 2012, pp. 708--717]. In this paper, we revisit the ranking algorithm using the linear programming framework. Special care is given to analyze the structural properties of the ranking algorithm in order to derive the linear programming constraints, of which one known as the boundary constraint requires totally new analysis and is crucial to the success of our linear program (LP). We use continuous linear programming 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 linear programming. Improving previous work, this paper achieves a theoretical performance ratio of $frac{2(5-sqrt{7})}{9} approx 0.523$ on arbitrary graphs. Read More: https://epubs.siam.org/doi/10.1137/140984051 | - |
dc.language | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP | - |
dc.relation.ispartof | SIAM Journal on Computing | - |
dc.rights | © [2018] Society for Industrial and Applied Mathematics. First Published in [SIAM Journal on Computing] in [v. 47 n. 4], published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.rights | This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. | - |
dc.subject | oblivious matching problem | - |
dc.subject | continuous linear programming | - |
dc.subject | ranking algorithm | - |
dc.title | Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming | - |
dc.type | Article | - |
dc.identifier.email | Chan, THH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, THH=rp01312 | - |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.1137/140984051 | - |
dc.identifier.scopus | eid_2-s2.0-85053598931 | - |
dc.identifier.hkuros | 318362 | - |
dc.identifier.volume | 47 | - |
dc.identifier.issue | 4 | - |
dc.identifier.spage | 1529 | - |
dc.identifier.epage | 1546 | - |
dc.identifier.isi | WOS:000443195600009 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 0097-5397 | - |