Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space

DOI10.1007/s11634-021-00481-4OpenAlexW4200036743WikidataQ114222062 ScholiaQ114222062MaRDI QIDQ6161667

Vladimir Shenmaier

Publication date: 27 June 2023

Published in: Advances in Data Analysis and Classification. ADAC (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11634-021-00481-4

zbMATH Keywords

discretizationclusteringEuclidean spacefacility locationgeometric optimizationhigh dimensionscandidate centers

Mathematics Subject Classification ID

Continuous location (90B85) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• Improved and simplified inapproximability for \(k\)-means
• NP-hardness of Euclidean sum-of-squares clustering
• Clustering to minimize the maximum intercluster distance
• Linear-size universal discretization of geometric center-based problems in fixed dimensions
• Complexity and approximation of the smallest \(k\)-enclosing ball problem
• On the complexity of some geometric problems in unbounded dimension
• Quadratic Time, Linear Space Algorithms for Gram-Schmidt Orthogonalization and Gaussian Sampling in Structured Lattices
• On the Complexity of Some Common Geometric Location Problems
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• Linear-time approximation schemes for clustering problems in any dimensions
• Approximate clustering via core-sets
• A PTAS for k-means clustering based on weak coresets
• Computing Minimum-Weight Perfect Matchings
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• An approximation scheme for a problem of search for a vector subset
• Approximate minimum enclosing balls in high dimensions using core-sets