# Optimal algorithms for approximate clustering

@inproceedings{Feder1988OptimalAF, title={Optimal algorithms for approximate clustering}, author={Tom{\'a}s Feder and Daniel H. Greene}, booktitle={STOC '88}, year={1988} }

In a clustering problem, the aim is to partition a given set of <italic>n</italic> points in <italic>d</italic>-dimensional space into <italic>k</italic> groups, called clusters, so that points within each cluster are near each other. Two objective functions frequently used to measure the performance of a clustering algorithm are, for any <italic>L<subscrpt>4</subscrpt></italic> metric, (a) the maximum distance between pairs of points in the same cluster, and (b) the maximum distance between… Expand

#### 459 Citations

FPT Approximation for Fair Minimum-Load Clustering

- Computer Science
- ArXiv
- 2021

This work makes substantial progress in understanding the structure of the minimum-load objective, advancing the frontiers of knowledge about the MLkC problem and achieving the first constant approximations for this problem in general and Euclidean metric spaces. Expand

A Fast Clustering Algorithm for Data with a Few Labeled Instances

- Mathematics, Computer Science
- Comput. Intell. Neurosci.
- 2015

A simple and fast clustering algorithm with the following property: if the ratio of the minimum split to the maximum diameter (RSD) of the optimal solution is greater than one, the algorithm returns optimal solutions for three clustering criteria. Expand

Clustering with Neighborhoods

- Computer Science
- ArXiv
- 2021

The systematic study of the clustering with neighborhoods problem is initiated, which generalizes the k-center problem to allow the covered objects to be a set of general disjoint convex objects C rather than just a point set P . Expand

Efficient approximation algorithms for clustering point-sets

- Computer Science, Mathematics
- Comput. Geom.
- 2010

An O(m+nlogk)-time 3-approximation algorithm and an O(km)-time (1+3)-approximating algorithm, where m is the total number of input points and k is the number of clusters, for the k-center clustering problem on point-sets. Expand

Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract)

- Computer Science, Mathematics
- SCG '94
- 1994

The optimum solution to the k-clustering problem is characterized by the ordinary Euclidean Voronoi diagram and the weighted Vor onoi diagram with both multiplicative and additive weights. Expand

Approximation Algorithms for Clustering to Minimize the Sum of Diameters

- Mathematics, Computer Science
- Nord. J. Comput.
- 2000

It is shown that, unless P = NP, for any ρ ≥ 1, there is no polynomial time approximation algorithm that can provide a performance guarantee of ρ even when the number of clusters is fixed at 3. Expand

Clustering to Maximize the Ratio of Split to Diameter

- Mathematics, Computer Science
- ICML
- 2012

This paper proposes a new criterion for measuring the goodness of clusters: the ratio of the minimum split to the maximum diameter, and the objective is to maximize the ratio. Expand

Testing of Clustering

- Mathematics, Computer Science
- SIAM Rev.
- 2004

This work studies the problem of clustering with respect to the diameter and the radius costs from within the framework of property testing and distinguishes between the case when X is (k,b)-clusterable and the case ... Expand

Fault Tolerant Clustering Revisited

- Mathematics, Computer Science
- CCCG
- 2013

In discrete k-center and k-median clustering, we are given a set of points P in a metric space M, and the task is to output a set C \subseteq ? P, |C| = k, such that the cost of clustering P using C… Expand

An optimal algorithm for approximate nearest neighbor searching fixed dimensions

- Computer Science, Mathematics
- JACM
- 1998

It is shown that it is possible to preprocess a set of data points in real D-dimensional space in O(kd) time and in additional space, so that given a query point q, the closest point of S to S to q can be reported quickly. Expand

#### References

SHOWING 1-10 OF 34 REFERENCES

An optimal algorithm for the all-nearest-neighbors problem

- Mathematics, Computer Science
- 27th Annual Symposium on Foundations of Computer Science (sfcs 1986)
- 1986

This work gives an O(nlogn) algorithm for the All-Nearest-Neighbors problem, for fixed dimension k and fixed metric Lq, and shows that the running time of this algorithm is optimal upto a constant. Expand

Clustering to Minimize the Maximum Intercluster Distance

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1985

An O(kn) approximation algorithm that guarantees solutions with an objective function value within two times the optimal solution value is presented and it is shown that this approximation algorithm succeeds as long as the set of points satisfies the triangular inequality. Expand

A Best Possible Heuristic for the k-Center Problem

- Computer Science, Mathematics
- Math. Oper. Res.
- 1985

A 2-approximation algorithm for the k-center problem with triangle inequality is presented, the key combinatorial object used is called a strong stable set, and the NP-completeness of the corresponding decision problem is proved. Expand

Optimal Packing and Covering in the Plane are NP-Complete

- Computer Science
- Inf. Process. Lett.
- 1981

This paper proves that even severely restricted instances of packing and covering problems remain NP-hard in two or more dimensions, and helps to fill the gap by showing that some very constrained intersection graph problems in two dimensions are not very constrained. Expand

Approximation Algorithms for NP-Complete Problems on Planar Graphs (Preliminary Version)

- Mathematics, Computer Science
- FOCS
- 1983

A general technique that can be used to obtain approximation algorithms for various NP-complete problems on planar graphs, which includes maximum independent set, maximum tile salvage, partition into triangles, maximum H-matching, minimum vertex cover, minimum dominating set, and minimum edge dominating set. Expand

On the Complexity of Clustering Problems

- Mathematics
- 1978

The class of discrete optimization problems may be partitioned into two subclasses PS and P?. PS is the subclass of problems which are known to be polynomial solvable. P? is the subclass of problems… Expand

On the Complexity of Some Common Geometric Location Problems

- Mathematics, Computer Science
- SIAM J. Comput.
- 1984

The p-center and the p-median problems relative to both the Euclidean and the rectilinear metrics are NP-hard and the reductions are from 3-satisfiability. Expand

Easy and hard bottleneck location problems

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1979

This work considers a bottleneck location problem on a graph and presents an efficient (polynomial time) algorithm for solving it, and shows that two other bottleneck location problems, finding K -centers and absolute K - centres of a graph appear to be very difficult to solve even for reasonably good approximate solutions. Expand

A unified approach to approximation algorithms for bottleneck problems

- Computer Science, Mathematics
- JACM
- 1986

In this paper a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP-complete problems in routing, location, and communication network design is… Expand

Fast algorithms for vector quantization picture coding

- Computer Science, Mathematics
- ICASSP '87. IEEE International Conference on Acoustics, Speech, and Signal Processing
- 1987

A data structure (k-d trees, developed by Bentley) is demonstrated to be appropriate for implementing exact nearest neighbor searching in time logarithmic in codebook size and is generalizable to any vector quantization application with the appropriate distortion measure. Expand