Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
no edit summary
Line 1:
Line 1:
The Degree of Segregation in Social Networks+Nicole Immorlica, Microsoft Research +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.+
== Title ==
== Title ==
−Revisiting the Ranking Algorithm for Greedy Randomized Matching on Arbitrary Graphs
== Speaker ==
== Speaker ==
−Hubert Chan, Department of Computer Science, The University of Hong Kong
== Abstract ==
== 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.
