Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
no edit summary
== Title ==
Revisiting the Ranking Algorithm for Greedy Randomized Matching on Arbitrary Graphs
== Speaker ==
Hubert Chan, Department of Computer Science, The University of Hong Kong
== 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.5000025
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 talk, 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. We believe our work achieves the currently best
theoretical performance ratio of 0.523 on arbitrary graphs.
Revisiting the Ranking Algorithm for Greedy Randomized Matching on Arbitrary Graphs
== Speaker ==
Hubert Chan, Department of Computer Science, The University of Hong Kong
== 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.5000025
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 talk, 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. We believe our work achieves the currently best
theoretical performance ratio of 0.523 on arbitrary graphs.
