Clustering to Minimize the Maximum Intercluster Distance
Explore this paper's citation graph
Summary
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.
- Type
- article
- Published
- 1985-01-01
- Cited by
- 2,126
- References
- 23
- Access
- Open access
- OpenAlex
- https://openalex.org/W1973264045
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:205092276
Keywords
Approximation algorithm, Mathematics, Cluster analysis, Triangle inequality, Combinatorics
References
- Michael R.Garey/David S.Johnson 著, "COMPUTERS AND INTRACTABILITY A guide to the Theory of NP-Completeness", FREEMAN, A5判変形判, 338+xii, \5,217, 1979
- Dynamic information and library processing
- Computer-oriented approaches to pattern recognition
- Fundamentals of Computer Algorithms
- The SMART Retrieval System—Experiments in Automatic Document Processing
- An Analysis of Some Graph Theoretical Cluster Techniques
- On Grouping for Maximum Homogeneity
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- A graph theoretic approach to the grouping of ordering data
- The Complexity of Near-Optimal Graph Coloring
- Reverberation at 75 kHz to a depth of 1 km in the Pacific Ocean—a negligible factor in attenuation
- Powers of graphs: A powerful approximation technique for bottleneck problems
- Pattern classification and scene analysis
- P-Complete Approximation Problems
- Admissible clustering procedures
- Geometry and Statistics: Problems at the Interface,
- Pattern Classification and Scene Analysis.
- Geometry and statistics: problems at the interface
- On the Complexity of Clustering Problems
- On the computational complexity of clustering and related problems
Cited by
- Diversity in Skylines
- Data mining techniques for detection of sleep arousals.
- ISI-Aware Channel Code Design for Molecular Communication via Diffusion
- Improved Fast Gauss Transform
- Summarizing certainty in uncertain data
- Are approximation algorithms for consensus clustering worthwhile?
- Providing bandwidth on demand services using optical network design and the silo network architecture
- A new point cloud simplification algorithm
- Towards hierarchical clustering
- Approximating min-max k-clustering
- A Review on Consensus Clustering Methods
- Hardness and Non-Approximability of Bregman Clustering Problems
- Fast Marching farthest point sampling
- Algorithmes exacts et exponentiels pour les problèmes NP-difficiles : domination, variantes et généralisations. (Excat exponential time algorithms for NP-hard problems : domination, variants and generalizations)
- Systematic clustering method for l-diversity model
- Intelligent analysis of aircraft flight data parameters
- Hierarchical traffic grooming in large-scale wdm networks
- Geometric Algorithms for Objects in Motion
- Deterministic clustering with data nets
- Finding Metric Structure in Information Theoretic Clustering
Related papers
- Approximation algorithms for the TSP with sharpened triangle inequality
- 35/44-approximation for Asymmetric Maximum TSP with Triangle Inequality
- An improved approximation algorithm for the ATSP with parameterized triangle inequality
- Approximation Algorithms for Clustering to Minimize the Sum of Diameters
- A 2 + ε approximation algorithm for the k-MST problem
- Efficient approximation algorithms for pairwise data clustering and applications