Approximation algorithms for stochastic clustering

David G. Harris; Shi Li; Thomas Pensyl; Aravind Srinivasan; Khoa Trinh

Approximation algorithms for stochastic clustering

David G. Harris
, Shi Li
, Thomas Pensyl
, Aravind Srinivasan
, Khoa Trinh

Department of Computer Science and Engineering

University at Buffalo

Research output: Contribution to journal › Conference article › peer-review

2 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	6038-6047
Number of pages	10
Journal	Advances in Neural Information Processing Systems
Volume	2018-December
State	Published - 2018
Event	32nd Conference on Neural Information Processing Systems, NeurIPS 2018 - Montreal, Canada Duration: Dec 2 2018 → Dec 8 2018

Keywords

Approximation algorithms
Clustering
K-center
K-median
Lottery

Cite this

@article{aa64b0a8916245439d766439555cbea5,

title = "Approximation algorithms for stochastic clustering",

abstract = "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 = "Approximation algorithms, Clustering, K-center, K-median, Lottery",

author = "Harris, \{David G.\} and Shi Li and Thomas Pensyl and Aravind Srinivasan and Khoa Trinh",

note = "Publisher Copyright: {\textcopyright} 2018 Curran Associates Inc.All rights reserved.; 32nd Conference on Neural Information Processing Systems, NeurIPS 2018 ; Conference date: 02-12-2018 Through 08-12-2018",

year = "2018",

language = "English",

volume = "2018-December",

pages = "6038--6047",

journal = "Advances in Neural Information Processing Systems",

issn = "1049-5258",

publisher = "Neural information processing systems foundation",

}

TY - JOUR

T1 - Approximation algorithms for stochastic clustering

AU - Harris, David G.

AU - Li, Shi

AU - Pensyl, Thomas

AU - Srinivasan, Aravind

AU - Trinh, Khoa

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Clustering

KW - K-center

KW - K-median

KW - Lottery

UR - https://www.scopus.com/pages/publications/85064808021

M3 - Conference article

SN - 1049-5258

VL - 2018-December

SP - 6038

EP - 6047

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

T2 - 32nd Conference on Neural Information Processing Systems, NeurIPS 2018

Y2 - 2 December 2018 through 8 December 2018

ER -

Approximation algorithms for stochastic clustering

Abstract

Keywords

Other files and links

Fingerprint

Cite this