A Best Possible Heuristic for the k-Center Problem

DOI10.1287/moor.10.2.180zbMath0565.90015OpenAlexW2073583237WikidataQ59760357 ScholiaQ59760357MaRDI QIDQ3680584

Publication date: 1985

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.10.2.180

zbMATH Keywords

NP-completeness triangle inequality complete graph location on networks strong stable set k-center problem 2- approximation algorithm best possible heuristic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Inventory, storage, reservoirs (90B05)

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

New approximation results for resource replication problems ⋮ Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem ⋮ A simple greedy approximation algorithm for the minimum connected \(k\)-center problem ⋮ A recurrence template for several parameters in series-parallel graphs ⋮ FICW: Frequent itemset based text clustering with window constraint ⋮ The \(p\)-neighbor \(k\)-center problem ⋮ Clustering to minimize the sum of cluster diameters ⋮ The mixed center location problem ⋮ Matroid and knapsack center problems ⋮ On hierarchical diameter-clustering and the supplier problem ⋮ Preclustering algorithms for imprecise points ⋮ Asymmetric \(k\)-center with minimum coverage ⋮ Topology-invariant similarity of nonrigid shapes ⋮ A heuristic for the p-center problem in graphs ⋮ The polygon burning problem ⋮ Clustering sparse binary data with hierarchical Bayesian Bernoulli mixture model ⋮ A new internal index based on density core for clustering validation ⋮ Hierarchy cost of hierarchical clusterings ⋮ Approximation algorithms for clustering with dynamic points ⋮ One-class classification with extreme learning machine ⋮ The Euclidean \(k\)-supplier problem in \(I R^2\) ⋮ Approximation algorithms for Hamming clustering problems ⋮ Designing and reporting on computational experiments with heuristic methods ⋮ Burning a graph is hard ⋮ On some variants of Euclidean \(k\)-supplier ⋮ The distance-constrained matroid median problem ⋮ On clustering with discounts ⋮ Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs ⋮ On ill-conceived initialization in archetypal analysis ⋮ An exact algorithm for the maximum probabilistic clique problem ⋮ Ordinal approximation for social choice, matching, and facility location problems given candidate positions ⋮ Full and partial symmetries of non-rigid shapes ⋮ Nonlinear dimensionality reduction by topologically constrained isometric embedding ⋮ A Gromov-Hausdorff framework with diffusion geometry for topologically-robust non-rigid shape matching ⋮ Centrality of trees for capacitated \(k\)-center ⋮ On the complexity of some problems of searching for a family of disjoint clusters ⋮ The Mixed Center Location Problem ⋮ Client assignment problems for latency minimization ⋮ On Metric Clustering to Minimize the Sum of Radii ⋮ Some variations on constrained minimum enclosing circle problem ⋮ Non-rigid Shape Correspondence Using Surface Descriptors and Metric Structures in the Spectral Domain ⋮ On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph ⋮ A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem ⋮ The connected disk covering problem ⋮ Lexicographic local search and the \(p\)-center problem. ⋮ Progressive scattered data filtering. ⋮ A self-stabilizing algorithm to maximal 2-packing with improved complexity ⋮ Complexity of some problems of quadratic partitioning of a finite set of points in Euclidean space into balanced clusters ⋮ A theory and algorithms for combinatorial reoptimization ⋮ New algorithms for a simple measure of network partitioning ⋮ VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION ⋮ Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs ⋮ Pivot selection: dimension reduction for distance-based indexing ⋮ Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem ⋮ Volume in general metric spaces ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ A Family of Unsupervised Sampling Algorithms ⋮ The fault-tolerant capacitated \(K\)-center problem ⋮ On minimum sum of radii and diameters clustering ⋮ Improved approximation algorithms for capacitated fault-tolerant \(k\)-center ⋮ Operations research and data mining ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs ⋮ Cluster ensembles: a survey of approaches with recent extensions and applications ⋮ The minimum weight \(t\)-composition of an integer ⋮ Complexity of the multi-service center problem ⋮ Faster balanced clusterings in high dimension ⋮ On metric clustering to minimize the sum of radii ⋮ An approximation algorithm for the edge-dilation \(k\)-center problem. ⋮ \(k\)-center problems with minimum coverage ⋮ A genetic algorithm for the maximum 2-packing set problem ⋮ Approximation algorithm for the kinetic robust \(k\)-center problem ⋮ Performance guarantees for hierarchical clustering ⋮ Asymmetry in \(k\)-center variants ⋮ Manifold Intrinsic Similarity ⋮ Solving thep-Center problem with Tabu Search and Variable Neighborhood Search ⋮ Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems ⋮ Fast Entropic Regularized Optimal Transport Using Semidiscrete Cost Approximation ⋮ Fast approximation algorithms for \(p\)-centers in large \(\delta\)-hyperbolic graphs ⋮ Partition of unity methods for signal processing on graphs ⋮ Mathematical Models and Search Algorithms for the Capacitated p-Center Problem ⋮ Reverse greedy is bad for \(k\)-center ⋮ K-center and K-median problems in graded distances ⋮ An adaptive probabilistic algorithm for online \(k\)-center clustering ⋮ APPROXIMATELY ISOMETRIC SHAPE CORRESPONDENCE BY MATCHING POINTWISE SPECTRAL FEATURES AND GLOBAL GEODESIC STRUCTURES ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms ⋮ Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints ⋮ On perturbation resilience of non-uniform \(k\)-center ⋮ The weighted \(k\)-center problem in trees for fixed \(k\) ⋮ Fault tolerant \(K\)-center problems ⋮ A new assignment rule to improve seed points algorithms for the continuous \(k\)-center problem ⋮ More on limited packings in graphs ⋮ One-way and round-trip center location problems ⋮ Unnamed Item ⋮ The probabilistic approach to limited packings in graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ Unnamed Item ⋮ 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

This page was built for publication: A Best Possible Heuristic for the k-Center Problem