2 papers
cs.DS2010
When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
Nikhil Bansal, Anupam Gupta, Jian Li +3
Consider a random graph model where each possible edge is present independently with some probability . Given these probabilities, we want to build a large/heavy matching…
cs.DS2010
Clustering with diversity
Jian Li, Ke Yi, Qin Zhang
We consider the {\em clustering with diversity} problem: given a set of colored points in a metric space, partition them into clusters such that each cluster has at least po…