Clustering to minimize the maximum intercluster distance

From MaRDI portal

Publication:1059958

Jump to:navigation, search

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

clustering approximation algorithm NP-completeness minimizing maximum intercluster distance triangular inequality

Mathematics Subject Classification ID

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

Related Items

Simplified group activity selection with group size constraints ⋮ New approximation results for resource replication problems ⋮ Generalized \(k\)-means in GLMs with applications to the outbreak of COVID-19 in the United States ⋮ A multi-dimensional approach to force-directed layouts of large graphs ⋮ Dynamic coresets ⋮ The \(p\)-neighbor \(k\)-center problem ⋮ Online unit clustering and unit covering in higher dimensions ⋮ FCM-based model selection algorithms for determining the number of clusters ⋮ The mixed center location problem ⋮ Matroid and knapsack center problems ⋮ Kinetic clustering of points on the line ⋮ A randomized algorithm for online unit clustering ⋮ On hierarchical diameter-clustering and the supplier problem ⋮ Space exploration via proximity search ⋮ The approximability of three-dimensional assignment problems with bottleneck objective ⋮ Topology-invariant similarity of nonrigid shapes ⋮ New algorithms for \(k\)-center and extensions ⋮ Trajectory clustering of points in \(\mathbb{R}\) ⋮ The polygon burning problem ⋮ Double bound method for solving the \(p\)-center location problem ⋮ A new initialization and performance measure for the rough \(k\)-means clustering ⋮ Hierarchy cost of hierarchical clusterings ⋮ Approximation algorithms for clustering with dynamic points ⋮ On packing time-respecting arborescences ⋮ Approximation algorithms for Hamming clustering problems ⋮ Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality ⋮ A distributed approximation algorithm for the bottleneck connected dominating set problem ⋮ The distance-constrained matroid median problem ⋮ A bad instance for \texttt{k-means++} ⋮ An incremental version of the \(k\)-center problem on boundary of a convex polygon ⋮ An indication of unification for different clustering approaches ⋮ Compact location problems ⋮ Complexity of control in judgment aggregation for uniform premise-based quota rules ⋮ New families of stable simplicial filtration functors ⋮ Near-optimal coresets of kernel density estimates ⋮ Nonlinear dimensionality reduction by topologically constrained isometric embedding ⋮ Centrality of trees for capacitated \(k\)-center ⋮ Only distances are required to reconstruct submanifolds ⋮ Sparse conjugate directions pursuit with application to fixed-size kernel models ⋮ On min-max \(r\)-gatherings ⋮ Covering moving points with anchored disks ⋮ Quantum speed-up for unsupervised learning ⋮ A connection between sports and matroids: how many teams can we beat? ⋮ The 2-center problem in three dimensions ⋮ The connected disk covering problem ⋮ Distance-based index structures for fast similarity search ⋮ Orphan-free anisotropic Voronoi diagrams ⋮ On the complexity of bribery with distance restrictions ⋮ Graph clustering ⋮ Some results of Christos Papadimitriou on internet structure, network routing, and web information ⋮ Adaptive initialization method based on spatial local information for \(k\)-means algorithm ⋮ Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem ⋮ Volume in general metric spaces ⋮ Combining gene expression profiles and drug activity patterns analysis: a relational clustering approach ⋮ Analysis of agglomerative clustering ⋮ The fault-tolerant capacitated \(K\)-center problem ⋮ Complexity and inapproximability results for balanced connected subgraph problem ⋮ Network community detection on metric space ⋮ Initializing \(k\)-means clustering by bootstrap and data depth ⋮ Improved approximation algorithms for capacitated fault-tolerant \(k\)-center ⋮ Control complexity in Borda elections: solving all open cases of offline control and some cases of online control ⋮ Incremental space-filling design based on coverings and spacings: improving upon low discrepancy sequences ⋮ Analysis of farthest point sampling for approximating geodesics in a graph ⋮ A streaming algorithm for 2-center with outliers in high dimensions ⋮ Constrained clustering by constraint programming ⋮ Approximation algorithms for geometric median problems ⋮ Complexity of the multi-service center problem ⋮ Faster balanced clusterings in high dimension ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Ectropy of diversity measures for populations in Euclidean space ⋮ Approximation algorithm for the kinetic robust \(k\)-center problem ⋮ Large group decision-making incorporating decision risk and risk attitude: a statistical approach ⋮ Performance guarantees for hierarchical clustering ⋮ A sampling-based exact algorithm for the solution of the minimax diameter clustering problem ⋮ Complexity of token swapping and its variants ⋮ Local fairness in hedonic games via individual threshold coalitions ⋮ Adaptive consensus reaching process with hybrid strategies for large-scale group decision making ⋮ Efficient approximation algorithms for clustering point-sets ⋮ Maximum-likelihood approximate nearest neighbor method in real-time image recognition ⋮ A linear-space algorithm for distance preserving graph embedding ⋮ Algorithmic aspects of 2-secure domination in graphs ⋮ The correntropy MACE filter ⋮ Partition of unity methods for signal processing on graphs ⋮ Parallel query processing on distributed clustering indexes ⋮ Near-optimal clustering in the \(k\)-machine model ⋮ Generalized \(p\)-center problems: Complexity results and approximation algorithms ⋮ Improved approximability and non-approximability results for graph diameter decreasing problems ⋮ Efficient systematic clustering method for \(k\)-anonymization ⋮ An empirical comparison between stochastic and deterministic centroid initialisation for K-means variations ⋮ Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints ⋮ On perturbation resilience of non-uniform \(k\)-center ⋮ Fault tolerant \(K\)-center problems ⋮ On Pareto optimality in social distance games ⋮ Complexity of shift bribery for iterative voting rules ⋮ Approximating uniform triangular meshes in polygons. ⋮ Complexity and approximability of minimum path-collection exact covers ⋮ Hexagonal unit network - a tool for proving the NP-completeness results of geometric problems ⋮ A constant-factor approximation algorithm for the \(k\)-median problem ⋮ A technique for obtaining true approximations for \(k\)-center with covering constraints ⋮ Fair colorful \(k\)-center clustering ⋮ A 2-phase approach for planning of hazardous waste collection using an unmanned aerial vehicle ⋮ Massively parallel and streaming algorithms for balanced clustering ⋮ An approximation algorithm for diversity-aware fair \(k\)-supplier problem ⋮ Generalized Alignment-Based Trace Clustering of Process Behavior ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Allocation of indivisible items with individual preference graphs ⋮ Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space ⋮ Faster distance-based representative skyline and \(k\)-center along Pareto front in the plane ⋮ Mixed-integer programming techniques for the minimum sum-of-squares clustering problem ⋮ Improved separated red-blue center clustering ⋮ Finding diameter-reducing shortcuts in trees ⋮ Stability and welfare in (dichotomous) hedonic diversity games ⋮ 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

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1059958&oldid=13072539"