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

DOI10.1007/978-3-030-58657-7_10zbMath1460.90183OpenAlexW3084574914MaRDI QIDQ4965103

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

Euclidean spacehigh dimensionsgeometric clusteringcontinuous facility locationapproximate centers

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Related Items (2)

Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ Approximation and complexity of the capacitated geometric median problem

Cites Work

• Unnamed Item
• Unnamed Item
• Clustering through continuous facility location problems
• Computational complexity and approximation for a generalization of the Euclidean problem on the Chebyshev center
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• Iterated nearest neighbors and finding minimal polytopes
• Exact and approximation algorithms for clustering
• Faster algorithms for the constrained \(k\)-means problem
• Complexity and approximation of the smallest \(k\)-enclosing ball problem
• Finding k points with minimum diameter and related problems
• Linear-time approximation schemes for clustering problems in any dimensions
• Approximate clustering via core-sets
• On coresets for k-means and k-median clustering
• On k-Median clustering in high dimensions
• An approximation scheme for a problem of search for a vector subset
• The problem of a minimal ball enclosing k points
• A Unified Framework for Clustering Constrained Data without Locality Property
• Approximate minimum enclosing balls in high dimensions using core-sets

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