Improved Approximations for Euclidean k-Means and k-Median, via Nested Quasi-Independent Sets

Improved Approximations for Euclidean k-Means and k-Median, via Nested Quasi-Independent Sets

Bibliographic Details
Main Authors:	Cohen-Addad, Vincent, Esfandiari, Hossein, Mirrokni, Vahab, Narayanan, Shyam
Other Authors:	Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format:	Article
Language:	English
Published:	ACM\|Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 2022
Online Access:	https://hdl.handle.net/1721.1/146412

Similar Items

Online k-means clustering
by: Cohen-Addad, V, et al.
Published: (2021)

Approximation algorithms for distributed and selfish agents
by: Mirrokni, Vahab S
Published: (2006)

A performance comparison of euclidean, manhattan and minkowski distances in k-means clustering
by: Haviluddin Haviluddin, et al.
Published: (2021)

Smooth Anonymity for Sparse Graphs
by: Epasto, Alessandro, et al.
Published: (2024)

Approximate k-means clustering through random projections
by: Persu, Elena-Mădălina
Published: (2015)

Parallel graph algorithms in constant adaptive rounds: theory meets practice
by: Behnezhad, Soheil, et al.
Published: (2021)

The Revised M-OF-K Runs Rules Based On Median Run Length
by: Low, , Chun Kit.
Published: (2011)

The Revised M-Of -K Runs Rules Based On Median Run Length
by: Low , Chun Kit
Published: (2011)

The revised m-of-k runs rule based on median run length
by: Low, Chun Kit., et al.
Published: (2013)

Approximating Submodular Functions Everywhere
by: Goemans, Michel X., et al.
Published: (2011)

Tight Approximation Algorithms for Maximum Separable Assignment Problems
by: Goemans, Michel X., et al.
Published: (2013)

Improving PAC exploration using the median of means
by: Pazis, Jason, et al.
Published: (2018)

Learning manifolds with k-means and k-flats
by: Canas, Guillermo D., et al.
Published: (2014)

Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching
by: Woodruff, David P., et al.
Published: (2018)

A K-means multivariate approach for clustering independent components from magnetoencephalographic data.
by: Spadone, S, et al.
Published: (2012)

K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance
by: Indyk, Piotr, et al.
Published: (2012)

The Number of Edges in k-Quasi-planar Graphs
by: Fox, Jacob, et al.
Published: (2013)

Comparing O’Brien test using mean, median, symmetric and asymmetric trimmed mean
by: Kamal, M., et al.
Published: (2022)

Local pointwise second derivative estimates for strong solutions to the σk-Yamabe equation on Euclidean domains
by: Duncan, JAJ, et al.
Published: (2021)

On Approximability of Satisfiable k-CSPs: II
by: Bhangale, Amey, et al.
Published: (2023)

On Approximability of Satisfiable k-CSPs: III
by: Bhangale, Amey, et al.
Published: (2023)

On approximability of satisfiable k -CSPs: I
by: Bhangale, Amey, et al.
Published: (2022)

Self-similar solutions to the mean curvature flow in Euclidean and Minkowski space
by: Halldórsson, Höskuldur Pétur
Published: (2014)

Testing k-wise independent distributions
by: Xie, Ning, Ph. D. Massachusetts Institute of Technology
Published: (2013)

Dimensionality reduction for k-means clustering
by: Musco, Cameron N. (Cameron Nicholas)
Published: (2016)

Approximating Buy-at-Bulk k-Steiner trees
by: Hajiaghayi, MohammadTaghi, et al.
Published: (2006)

Fuzzy rank cluster top k Euclidean distance and triangle based algorithm for magnetic field indoor positioning system
by: Bundak, Caceja Elyca, et al.
Published: (2021)

Pattern discovery using k-means algorithm
by: Ahmed, Almahdi Mohammed, et al.
Published: (2014)

Asymptotic properties of bivariate k-means clusters
by: Wong, M. Anthony.
Published: (2009)

Private k-means clustering : algorithms and applications
by: Xiang, Chongyuan
Published: (2017)

Toward misreading : assembling (k)new meaning
by: Dennis, Nolan Oswald
Published: (2018)

A study of the median run length (MRL) performance of the EWMA t chart for the mean
by: Chin, W.S., et al.
Published: (2012)

A Comparative Study Of The Mean And Median Rainfall Patterns In Northwest Peninsular Malaysia.
by: Chan, Ngai Weng
Published: (1990)

PET image reconstruction incorporating 3D mean-median sinogram filtering
by: Mokri, Siti Salasiah, et al.
Published: (2016)

Optimal design of the synthetic chart for the process mean based on median run length
by: Khoo, Michael B. C., et al.
Published: (2013)

Model-independent measurement of the CKM angle $γ$ using $B^0 \to D K^{\ast 0}$ decays with $D \to K_{S}^{0} π^{+} π^{-}$ and $K_{S}^{0} K^{+} K^{-}$
by: LHCb Collaboration, et al.
Published: (2016)

Lakatos and the Euclidean programme
by: Paseau, AC, et al.
Published: (2024)

Euclidean spacetime functionalism
by: Read, J, et al.
Published: (2022)

k-means aperture optimization applied to Kepler K2 time series photometry of Titan
by: Parker, AH, et al.
Published: (2019)

Model-independent measurement of the CKM angle γ using B0 → DK∗0 decays with D → K S 0 π + π − and K S 0 K+K−
by: Aaij, R., et al.
Published: (2017)