Timezone: »

 
Poster
Approximation algorithms for stochastic clustering
David Harris · Shi Li · Aravind Srinivasan · Khoa Trinh · Thomas Pensyl

Tue Dec 04 02:00 PM -- 04:00 PM (PST) @ Room 517 AB #134
in Tue Poster Session B »

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.

Keywords: Combinatorial Optimization · Fairness, Accountability, and Transparency · Computational Complexity
[ Paper]  [ Poster] 

Author Information

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.

Khoa Trinh
Thomas Pensyl

More from the Same Authors