Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
no edit summary
Line 1:
Line 1:
Revisiting the Ranking Algorithm for Greedy Randomized Matching on Arbitrary Graphs+Hubert Chan, Department of Computer Science, The University of Hong Kong+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.
== Title ==
== Title ==
−The Degree of Segregation in Social Networks
== Speaker ==
== Speaker ==
−Nicole Immorlica, Microsoft Research
== Abstract ==
== Abstract ==
−In 1969, economist Thomas Schelling introduced a landmark model of racial segregation in which individuals move out of neighborhoods where their ethnicity constitutes a minority. Simple simulations of Schelling's model suggest that this local behavior can cause global segregation effects. In this talk, we provide a rigorous analysis of Schelling's model on ring networks. Our results show that, in contrast to prior interpretations, the outcome is nearly integrated: the average size of an ethnically-homogenous region is independent of the size of the society and only polynomial in the size of a neighborhood.
−Joint work with Christina Brandt, Gautam Kamath, and Robert D. Kleinberg.
−