Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions

DOI10.1007/978-3-030-58657-7_10MaRDI QIDQ4965103zbMATH OpenOpenAlexFDO

Authors Vladimir Shenmaier

Publication date 25 February 2021

Published in Mathematical Optimization Theory and Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-58657-7_10

zbMATH Keywords

high dimensionsEuclidean spacegeometric clusteringcontinuous facility locationapproximate centers

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Recommendations

• Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space
• Linear-size universal discretization of geometric center-based problems in fixed dimensions
• Solving the discrete \(l_p\)-approximation problem by a method of centers
• Discretization and affine approximation in high dimensions
• The generalized discrete ‐centroid problem
• scientific article; zbMATH DE number 2079186
• An exact method for the discrete \((r|p)\)-centroid problem
• An optimal generalization of the centerpoint theorem, and its extensions
• Generalizations of the centroid with an application in stochastic geometry

Cites work

• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 5019895 (Why is no real title available?)
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• A unified framework for clustering constrained data without locality property
• 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
• Clustering through continuous facility location problems
• Complexity and approximation of the smallest \(k\)-enclosing ball problem
• Computational complexity and approximation for a generalization of the Euclidean problem on the Chebyshev center
• Exact and approximation algorithms for clustering
• Faster algorithms for the constrained k-means problem
• Finding k points with minimum diameter and related problems
• 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 coresets for k-means and k-median clustering
• The problem of a minimal ball enclosing k points

Cited in

(3)

• Approximation and complexity of the capacitated geometric median problem
• Linear-size universal discretization of geometric center-based problems in fixed dimensions
• scientific article; zbMATH DE number 2079728 (Why is no real title available?)

This page was built for publication: Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions

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