Approximability results for the $p$-centdian and the converse centdian problems
From MaRDI portal
Publication:6045453
DOI10.46298/dmtcs.6877arXiv2011.00130OpenAlexW3097305407MaRDI QIDQ6045453
Publication date: 31 May 2023
Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2011.00130
computational complexitycombinatorial optimizationapproximation algorithmNP-completenetwork location\(p\)-centdian problemconverse centdian problem
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new polynomial-time algorithm for linear programming
- Clustering to minimize the maximum intercluster distance
- A heuristic for the p-center problem in graphs
- Easy and hard bottleneck location problems
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Location analysis: a synthesis and survey
- A bibliography for some fundamental problem categories in discrete location science
- Solving two location models with few facilities by using a hybrid heuristic: a real health resources case
- A linear time algorithm for connected \(p\)-centdian problem on block graphs
- Centdian Computation in Cactus Graphs
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- What you should know about location modeling
- State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
- Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
- Probabilistic Analysis of a Relaxation for the k-Median Problem
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- An Algorithmic Approach to Network Location Problems. II: Thep-Medians
- A Greedy Heuristic for the Set-Covering Problem
- Finite Dominating Sets for Network Location Problems
- Finding Minimal Center-Median Convex Combination (Cent-Dian) of a Graph
- Towards a theory of domination in graphs
- Bicriteria Network Design Problems
- How to Allocate Network Centers
- A polynomial algorithm for thep-centdian problem on a tree
- Local Search Heuristics for k-Median and Facility Location Problems
- Routing to Multiple Destinations in Computer Networks
- Genetic algorithm to solve the p-centre and p-radius problem on a network
- Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems
- The generalized \(p\)-centdian on network
