Approximation algorithms for stochastic clustering
Authors: David Harris, Shi Li, Aravind Srinivasan, Khoa Trinh, Thomas Pensyl
NeurIPS 2018 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Collaboration | David G. Harris Department of Computer Science University of Maryland, College Park, MD 20742 EMAIL, Shi Li University at Buffalo Buffalo, NY. EMAIL, Thomas Pensyl Bandwidth, Inc. Raleigh, NC EMAIL, Aravind Srinivasan Department of Computer Science and Institute for Advanced Computer Studies University of Maryland, College Park, MD 20742 EMAIL, Khoa Trinh Google Mountain View, CA 94043 EMAIL |
| Pseudocode | Yes | Algorithm 1 GREEDYCLUSTER(F, w), Algorithm 2 Iterative rounding algorithm for chance k-coverage, Algorithm 3 Rounding algorithm for k-coverage for uniform p or uniform r., Algorithm 4 Rounding algorithm for k-supplier, Algorithm 5 Rounding algorithm for k-center, Algorithm 7 Partial-cluster based algorithm for k-center |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the described methodology or provide links to a code repository. |
| Open Datasets | No | This is a theoretical research paper focusing on algorithm design and approximation ratios, and as such, it does not involve dataset training or require information about publicly available training datasets. |
| Dataset Splits | No | This is a theoretical research paper, and it does not describe experimental validation or data splits. |
| Hardware Specification | No | This is a theoretical research paper focused on algorithm design and analysis, and therefore, it does not describe any specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical research paper, and it does not specify software dependencies with version numbers used for experiments. |
| Experiment Setup | No | This is a theoretical research paper that focuses on algorithm design and analysis, and thus, it does not include details on experimental setup parameters like hyperparameters or training settings. |