We consider stochastic settings for clustering, and develop provably-good (approximation) algorithms for a number of these notions. These algorithms allow one to obtain better approximation ratios compared to the usual deterministic clustering setting. Additionally, they offer a number of advantages including providing fairer clustering and clustering which has better long-term behavior for each user. In particular, they ensure that every user is guaranteed to get good service (on average). We also complement some of these with impossibility results.
David Harris (University of Maryland)
Shi Li (University at Buffalo)
Aravind Srinivasan (University of Maryland College Park)
Aravind Srinivasan is a Professor with the Department of Computer Science and UMIACS at UMD, College Park. He received his undergraduate degree from the Indian Institute of Technology, Madras, and his Ph.D. from Cornell University. He was a postdoctoral researcher at the Institute for Advanced Study in Princeton and at DIMACS. Srinivasan's research interests are in randomized algorithms, E-commerce, public health, networking, social networks, and combinatorial optimization, as well as in the growing confluence of algorithms, networks, and randomness, in fields including the social Web, machine learning, biology, and energy. He has published more than 115 papers in these areas, in fora including Nature, Journal of the ACM, IEEE/ACM Transactions on Networking, and the SIAM Journal on Computing. He is Editor-in-Chief of the ACM Transactions on Algorithms, Managing Editor for Theory of Computing, and Associate Editor of Networks. Srinivasan is a Fellow of four professional societies: ACM, AAAS, IEEE and EATCS. He received a Distinguished Alumnus Award from his alma mater IIT Madras. He also received the Distinguished Faculty Award from the Board of Visitors of the College of Computing, Mathematical, and Natural Sciences (University of Maryland) in 2016. He received a Data Science Research Award from Adobe, Inc. in 2017.
More from the Same Authors
2021 Poster: Fair Clustering Under a Bounded Cost »
Seyed Esmaeili · Brian Brubach · Aravind Srinivasan · John Dickerson
2021 Poster: Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes »
Brian Brubach · Nathaniel Grammel · Will Ma · Aravind Srinivasan
2019 Poster: Facility Location Problem in Differential Privacy Model Revisited »
Yunus Esencayi · Marco Gaboardi · Shi Li · Di Wang
2018 Poster: Distributed $k$-Clustering for Data with Heavy Noise »
Shi Li · Xiangyu Guo
2018 Spotlight: Distributed $k$-Clustering for Data with Heavy Noise »
Shi Li · Xiangyu Guo