| Line 1: |
Line 1: |
| | == Title == | | == Title == |
| − | Revisiting the Ranking Algorithm for Greedy Randomized Matching on Arbitrary Graphs
| + | The Degree of Segregation in Social Networks |
| | | | |
| | == Speaker == | | == Speaker == |
| − | Hubert Chan, Department of Computer Science, The University of Hong Kong
| + | Nicole Immorlica, Microsoft Research |
| | | | |
| | == Abstract == | | == Abstract == |
| − | Motivated by online advertisement and exchange settings, greedy
| + | 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. |
| − | 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.
| + | Joint work with Christina Brandt, Gautam Kamath, and Robert D. Kleinberg. |
| − | 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.
| |