Linear-size universal discretization of geometric center-based problems in fixed dimensions

DOI10.1007/S10878-021-00790-6MaRDI QIDQ2125228zbMATH OpenOpenAlexFDO

Authors Vladimir Shenmaier

Publication date 13 April 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.10900

zbMATH Keywords

approximate centersclusteringdiscretizationfacility locationgeometric optimizationmetric space

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Abstract: Many geometric optimization problems can be reduced to finding points in space (centers) minimizing an objective function which continuously depends on the distances from the centers to given input points. Examples are $k$-Means, Geometric $k$-Median/Center, Continuous Facility Location, $m$-Variance, etc. We prove that, for any fixed $varepsilon>0$, every set of $n$ input points in fixed-dimensional space with the metric induced by any vector norm admits a set of $O(n)$ candidate centers which can be computed in almost linear time and which contains a $(1+varepsilon)$-approximation of each point of space with respect to the distances to all the input points. It gives a universal approximation-preserving reduction of geometric center-based problems with arbitrary continuity-type objective functions to their discrete versions where the centers are selected from a fairly small set of candidates. The existence of such a linear-size set of candidates is also shown for any metric space of fixed doubling dimension.

Recommendations

• Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions
• Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space
• Discrete rectilinear 2-center problems
• scientific article; zbMATH DE number 2079186
• A near-linear algorithm for the planar segment-center problem
• An optimal approximation algorithm for the rectilinear m-center problem
• Approximation algorithms for orthogonal line centers
• Approximation algorithms for orthogonal line centers
• scientific article; zbMATH DE number 1003238
• scientific article; zbMATH DE number 1588326

Cites work

• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• An approximation scheme for a problem of search for a vector subset
• Approximate clustering via core-sets
• Approximate minimum enclosing balls in high dimensions using core-sets
• Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster
• Bypassing the embedding
• Clustering through continuous facility location problems
• Complexity and approximation of the smallest \(k\)-enclosing ball problem
• Exact and approximation algorithms for clustering
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Finding k points with minimum diameter and related problems
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 5019895 (Why is no real title available?)
• Iterated nearest neighbors and finding minimal polytopes
• Linear-time approximation schemes for clustering problems in any dimensions
• On k-Median clustering in high dimensions
• On approximate geometric \(k\)-clustering
• On coresets for k-means and k-median clustering
• Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions
• The approximate rank of a matrix and its algorithmic applications

Cited in

(2)

• Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions
• Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space

This page was built for publication: Linear-size universal discretization of geometric center-based problems in fixed dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2125228)