Local search yields a PTAS for $k$-means in doubling metrics (Q4634026)

scientific article; zbMATH DE number 7051395

Language	Label	Description	Also known as
default for all languages	No label defined
English	Local search yields a PTAS for $k$-means in doubling metrics	scientific article; zbMATH DE number 7051395

Statements

instance of

scholarly article

0 references

title

Local Search Yields a PTAS for $k$-Means in Doubling Metrics (English)

0 references

author

Zachary Friggstad

0 references

Mohsen Rezapour

0 references

Mohammad Salavatipour

0 references

published in

SIAM Journal on Computing

0 references

publication date

7 May 2019

0 references

full work available at URL

https://arxiv.org/abs/1603.08976

0 references

zbMATH Keywords

$k$-means

0 references

polynomial time approximation scheme

0 references

doubling metrics

0 references

describes a project that uses

k-means++

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

NP-hardness of Euclidean sum-of-squares clustering

0 references

Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

0 references

Q4542527

0 references

Smoothed analysis of the $k$-means method

0 references

Q3601533

0 references

Q2934696

0 references

Local search heuristic for k-median and facility location problems

0 references

Local Search Heuristics for k-Median and Facility Location Problems

0 references

The hardness of approximation of Euclidean $k$-means

0 references

Approximate clustering via core-sets

0 references

On variants of $k$-means clustering

0 references

An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization

0 references

A dependent LP-rounding approach for the $k$-median problem

0 references

On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications

0 references

Effectiveness of local search for geometric optimization

0 references

Approximation schemes for clustering problems

0 references

Clustering large graphs via the singular value decomposition

0 references

A tight bound on approximating arbitrary metrics by tree metrics

0 references

A PTAS for k-means clustering based on weak coresets

0 references

Turning big data into tiny data: constant-size coresets for $k$-means, PCA and projective clustering

0 references

Local search yields a PTAS for $k$-means in doubling metrics

0 references

Smaller coresets for $k$-median and $k$-means clustering

0 references

On coresets for k-means and k-median clustering

0 references

How fast is the $k$-means method?

0 references

A local search approximation algorithm for $k$-means clustering

0 references

Linear-time approximation schemes for clustering problems in any dimensions

0 references

Universal ${\epsilon}$-approximators for integrals

0 references

A 1.488 approximation algorithm for the uncapacitated facility location problem

0 references

Approximating k-median via pseudo-approximation

0 references

Least squares quantization in PCM

0 references

The Planar k-Means Problem is NP-Hard

0 references

On approximate geometric $k$-clustering

0 references

Polynomial-time approximation schemes for geometric min-sum median clustering

0 references

The effectiveness of Lloyd-type methods for the $k$-means problem

0 references

Bypassing the embedding

0 references

$k$-means requires exponentially many iterations even in the plane

0 references

$k$-means requires exponentially many iterations even in the plane

0 references

Identifiers

zbMATH Open document ID

1422.68296

0 references

DOI

10.1137/17M1127181

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4634026

Local search yields a PTAS for \(k\)-means in doubling metrics (Q4634026)

Statements

Identifiers

Sitelinks

Mathematics(1 entry)