Clustering to minimize the maximum intercluster distance

DOI10.1016/0304-3975(85)90224-5zbMath0567.62048OpenAlexW1973264045WikidataQ57568243 ScholiaQ57568243MaRDI QIDQ1059958

Teofilo F. Gonzalez

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90224-5

zbMATH Keywords

clusteringapproximation algorithmNP-completenessminimizing maximum intercluster distancetriangular inequality

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Graph theory (including graph drawing) in computer science (68R10)

Related Items (only showing first 100 items - show all)

On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality ⋮ Uniformity of Point Samples in Metric Spaces Using Gap Ratio ⋮ A Technique for Obtaining True Approximations for k-Center with Covering Constraints ⋮ Fair Colorful k-Center Clustering ⋮ Complexity of the multi-service center problem ⋮ Altruistic Hedonic Games ⋮ A mixed breadth-depth first strategy for the branch and bound tree of Euclidean \(k\)-center problems ⋮ Unnamed Item ⋮ The Euclidean \(k\)-supplier problem in \(I R^2\) ⋮ COMPUTING k CENTERS OVER STREAMING DATA FOR SMALL k ⋮ On some variants of Euclidean \(k\)-supplier ⋮ On clustering with discounts ⋮ Privacy in Elections: k-Anonymizing Preference Orders ⋮ Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls ⋮ Uniformity of Point Samples in Metric Spaces Using Gap Ratio ⋮ Unnamed Item ⋮ Stateless Information Dissemination Algorithms ⋮ Approximability results for the $p$-centdian and the converse centdian problems ⋮ Min-Max-Min Optimization with Smooth and Strongly Convex Objectives ⋮ Determinantal consensus clustering ⋮ Approximation algorithms for the individually fair \(k\)-center with outliers ⋮ Compact location problems with budget and communication constraints ⋮ Immune sets in monotone infection rules. Characterization and complexity ⋮ A vertex weighting-based double-tabu search algorithm for the classical \(p\)-center problem ⋮ Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition ⋮ Universal Algorithms for Clustering Problems ⋮ Clustering with faulty centers ⋮ Quasi-uniform designs with optimal and near-optimal uniformity constant ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ A parameterized approximation algorithm for the multiple allocation \(k\)-hub center ⋮ Approximation algorithms for diversity-bounded center problems ⋮ Augmenting graphs to minimize the radius ⋮ The Euclidean k-Supplier Problem ⋮ Approximability results for the converse connectedp-centre problem^† ⋮ Complexity and approximability of certain bicriteria location problems ⋮ The Mixed Center Location Problem ⋮ Constant-factor approximation algorithms for some maximin multi-clustering problems ⋮ Fully dynamic clustering and diversity maximization in doubling metrics ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The \(p\)-center problem under locational uncertainty of demand points ⋮ On the parameterized complexity of clustering problems for incomplete data ⋮ Non-rigid Shape Correspondence Using Surface Descriptors and Metric Structures in the Spectral Domain ⋮ Unnamed Item ⋮ Allocating indivisible items with minimum dissatisfaction on preference graphs ⋮ Hedonic diversity games revisited ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ Unnamed Item ⋮ An Initialization Method Based on Hybrid Distance for k-Means Algorithm ⋮ A graph-theoretic approach on optimizing informed-node selection in multi-agent tracking control ⋮ An Optimal Incremental Algorithm for Minimizing Lateness with Rejection ⋮ On the cost of essentially fair clusterings ⋮ Small Space Stream Summary for Matroid Center ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ JOINT SEPARATION OF GEOMETRIC CLUSTERS AND THE EXTREME IRREGULARITIES OF REGULAR POLYHEDRA ⋮ Robustness among multiwinner voting rules ⋮ Unnamed Item ⋮ ALMOST OPTIMAL SOLUTIONS TO k-CLUSTERING PROBLEMS ⋮ Minimum-diameter covering problems ⋮ Facility location with dynamic distance functions ⋮ Unnamed Item ⋮ On Min-Max r-Gatherings ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ The clever shopper problem ⋮ Deformable spanners and applications ⋮ Mixed fault tolerance in server assignment: combining reinforcement and backup ⋮ Data Exploration by Representative Region Selection: Axioms and Convergence ⋮ Robust \(k\)-center with two types of radii ⋮ Sparse Approximation via Generating Point Sets ⋮ Covering convex polygons by two congruent disks ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction ⋮ Robust \(k\)-center with two types of radii ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Clustering in Hilbert’s Projective Geometry: The Case Studies of the Probability Simplex and the Elliptope of Correlation Matrices ⋮ Online unit covering in Euclidean space ⋮ Solving \(k\)-center problems involving sets based on optimization techniques ⋮ Unnamed Item ⋮ Generalized Center Problems with Outliers ⋮ Approximation algorithms for hierarchical location problems ⋮ An adaptive probabilistic algorithm for online \(k\)-center clustering ⋮ APPROXIMATELY ISOMETRIC SHAPE CORRESPONDENCE BY MATCHING POINTWISE SPECTRAL FEATURES AND GLOBAL GEODESIC STRUCTURES ⋮ Bayesian Decision Making in Groups is Hard ⋮ On interval and circular-arc covering problems ⋮ Unnamed Item ⋮ Approximate Range Queries for Clustering ⋮ New Algorithms for k-Center and Extensions ⋮ Optimization on Lie manifolds and pattern recognition ⋮ A FAST IMPLEMENTATION OF THE ISODATA CLUSTERING ALGORITHM ⋮ Constrained k-Center Problem on a Convex Polygon ⋮ Group-Valued Regularization for Motion Segmentation of Articulated Shapes ⋮ Covering convex polygons by two congruent disks ⋮ Gaussian Process Landmarking on Manifolds ⋮ Gaussian Process Landmarking for Three-Dimensional Geometric Morphometrics ⋮ Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results ⋮ Graph induced complex on point data ⋮ Simplified group activity selection with group size constraints

Cites Work

• Computer-oriented approaches to pattern recognition
• On Grouping for Maximum Homogeneity
• The Complexity of Near-Optimal Graph Coloring
• P-Complete Approximation Problems
• An Analysis of Some Graph Theoretical Cluster Techniques
• Automatische Klassifikation
• Admissible clustering procedures
• A graph theoretic approach to the grouping of ordering data
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Clustering to minimize the maximum intercluster distance