Anonymous

Changes

From Theory

CATS-Mar-15-2013 (view source)

Revision as of 15:06, 18 July 2013

767 bytes added ,  15:06, 18 July 2013
no edit summary
Line 1: Line 1:  
== Title ==
 
== Title ==
−
The Degree of Segregation in Social Networks
+
Revisiting the Ranking Algorithm for Greedy Randomized Matching on Arbitrary Graphs
    
== Speaker ==
 
== Speaker ==
−
Nicole Immorlica,  Microsoft Research
+
Hubert Chan,  Department of Computer Science, The University of Hong Kong
    
== 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.  
+
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.
   −
Joint work with Christina Brandt, Gautam Kamath, and Robert D. Kleinberg.
+
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.
Retrieved from "https://wiki.cs.umd.edu/theory/view/Special:MobileDiff/1705"