A Fully Polynomial-Time Approximation Scheme for a Special Case of a Balanced 2-Clustering Problem
From MaRDI portal
Publication:3133212
DOI10.1007/978-3-319-44914-2_15zbMath1380.68401OpenAlexW2559584927MaRDI QIDQ3133212
Anna Motkova, Alexander Kel'Manov
Publication date: 13 February 2018
Published in: Discrete Optimization and Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-44914-2_15
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems, Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster, 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence, Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center, Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem, Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space
