A simple heuristic for the p-centre problem
From MaRDI portal
Publication:761233
We describe a simple heuristic for determining the p-centre of a finite set of weighted points in an arbitrary metric space. The computational effort is O(np) for an n-point set. We show that the ratio of the objective function value of the heuristic solution to that of the optimum is bounded by \(\min (3,1+\alpha)\), where \(\alpha\) is the maximum weight divided by the minimum weight of points in the set.
Recommendations
Cites work
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- Easy and hard bottleneck location problems
- On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
- On the Complexity of Some Common Geometric Location Problems
- Optimal packing and covering in the plane are NP-complete
- The p-Centre Problem-Heuristic and Optimal Algorithms
Cited in
(57)- Location problems
- A heuristic for the p-center problem in graphs
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- A new assignment rule to improve seed points algorithms for the continuous \(k\)-center problem
- An improvement and an extension of the Elzinga \& Hearn's algorithm to the 1-center problem in \(\mathbb{R}^ n\) with \(l_{2b}\)-norms
- Compact location problems
- Lexicographic local search and the \(p\)-center problem.
- Fault tolerant \(K\)-center problems
- A theory and algorithms for combinatorial reoptimization
- \(k\)-center problems with minimum coverage
- Fast approximation algorithms for \(p\)-centers in large \(\delta\)-hyperbolic graphs
- A constant-factor approximation algorithm for the k-median problem
- Clustering to minimize the sum of cluster diameters
- A framework for demand point and solution space aggregation analysis for location models
- Designing and reporting on computational experiments with heuristic methods
- Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints
- The weighted \(k\)-center problem in trees for fixed \(k\)
- Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs
- The 1-center problem in the plane with independent random weights
- The maximal dispersion problem and the ``first point outside the neighbourhood heuristic
- On the parameterized complexity of clustering problems for incomplete data
- A simple greedy approximation algorithm for the minimum connected k-center problem
- Insertion heuristics for central cycle problems
- The p-Centre Problem-Heuristic and Optimal Algorithms
- Heuristic methods for thep-center problem
- A Best Possible Heuristic for the k-Center Problem
- scientific article; zbMATH DE number 3960894 (Why is no real title available?)
- scientific article; zbMATH DE number 4021197 (Why is no real title available?)
- scientific article; zbMATH DE number 4045779 (Why is no real title available?)
- scientific article; zbMATH DE number 4066949 (Why is no real title available?)
- scientific article; zbMATH DE number 34574 (Why is no real title available?)
- scientific article; zbMATH DE number 123788 (Why is no real title available?)
- The connected p-center problem on block graphs with forbidden vertices
- On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph
- Solving thep-Center problem with Tabu Search and Variable Neighborhood Search
- The fault-tolerant capacitated \(K\)-center problem
- Facility location with dynamic distance functions
- On cost-aware biased respondent group selection for minority opinion survey
- Grouping objects in multi-band images using an improved eigenvector-based algorithm
- Min-Max-Min Optimization with Smooth and Strongly Convex Objectives
- Compact location problems with budget and communication constraints
- Complexity and approximability of certain bicriteria location problems
- A constructive heuristic for the uniform capacitated vertex \(k\)-center problem
- From data completion to problems on hypercubes: a parameterized analysis of the independent set problem
- From data completion to problems on hypercubes: a parameterized analysis of the independent set problem
- Designing a sports orienteering contest: physical versus cognitive skills in rogaining
- Differentially private k-center problems
- Improved polynomial-time approximations for clustering with minimum sum of radii or diameters
- Finding a cluster in incomplete data
- An approximation algorithm for the edge-dilation \(k\)-center problem.
- Sketching persistence diagrams
- A sparse Delaunay filtration
- Approximation algorithms for clustering with minimum sum of radii, diameters, and squared radii
- A sparse multicover bifiltration of linear size
- On parallel k-center clustering
- Demand point aggregation for planar covering location models
- The stochastic p-hub center problem with service-level constraints
This page was built for publication: A simple heuristic for the p-centre problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q761233)
