File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleRanking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints
Authors
Issue Date2014
PublisherSociety for Industrial and Applied Mathematics (SIAM).
Citation
Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms: Portland, Oregon, USA, 5-7 January 2014, p. 1112-1122 How to Cite?
AbstractMotivated 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 algorithm achieves performance ratio 0.5+ ∊ (where ) 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. 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 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. Our work achieves the currently best theoretical performance ratio of on arbitrary graphs. Moreover, experiments suggest that Ranking cannot perform better than 0.724 in general.
Persistent Identifierhttp://hdl.handle.net/10722/201102
ISBN

 

DC FieldValueLanguage
dc.contributor.authorChan, HTHen_US
dc.contributor.authorChen, Fen_US
dc.contributor.authorWu, Xen_US
dc.contributor.authorZhao, Zen_US
dc.date.accessioned2014-08-21T07:13:34Z-
dc.date.available2014-08-21T07:13:34Z-
dc.date.issued2014en_US
dc.identifier.citationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms: Portland, Oregon, USA, 5-7 January 2014, p. 1112-1122en_US
dc.identifier.isbn9781611973389-
dc.identifier.urihttp://hdl.handle.net/10722/201102-
dc.description.abstractMotivated 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 algorithm achieves performance ratio 0.5+ ∊ (where ) 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. 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 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. Our work achieves the currently best theoretical performance ratio of on arbitrary graphs. Moreover, experiments suggest that Ranking cannot perform better than 0.724 in general.-
dc.languageengen_US
dc.publisherSociety for Industrial and Applied Mathematics (SIAM).-
dc.relation.ispartofAnnual ACM-SIAM Symposium on Discrete Algorithmsen_US
dc.titleRanking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraintsen_US
dc.typeConference_Paperen_US
dc.identifier.emailChan, HTH: hubert@cs.hku.hken_US
dc.identifier.authorityChan, HTH=rp01312en_US
dc.identifier.doi10.1137/1.9781611973402.82-
dc.identifier.hkuros232589en_US
dc.identifier.spage1112-
dc.identifier.epage1122-
dc.publisher.placePhiladelphia-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats