Approximability of the dispersed p-neighbor k-supplier problem

DOI10.1016/J.DAM.2020.10.007MaRDI QIDQ2217474zbMATH OpenOpenAlexFDO

Authors Martijn van Ee

Publication date 29 December 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2020.10.007

zbMATH Keywords

\(k\)-center\(k\)-supplierapproximation algorithmsdispersioninapproximability

Mathematics Subject Classification ID

Approximation algorithms (68W25) Queues and service in operations research (90B22) Discrete location and assignment (90B80) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• The Euclidean k-supplier problem
• The Euclidean \(k\)-supplier problem
• Fault tolerant \(K\)-center problems
• Heuristic and Special Case Algorithms for Dispersion Problems
• Approximation algorithms for dispersion problems

Cites work

• A Best Possible Heuristic for the k-Center Problem
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Clustering to minimize the maximum intercluster distance
• Dispersing Obnoxious Facilities on a Graph
• Easy and hard bottleneck location problems
• Fault tolerant \(K\)-center problems
• Heuristic and Special Case Algorithms for Dispersion Problems
• Obnoxious Facility Location on Graphs
• On the Complexity of Some Common Geometric Location Problems
• On the hardness of approximating minimum vertex cover
• Reducibility among combinatorial problems
• Some optimal inapproximability results
• The p-neighbor k-center problem
• The design of approximation algorithms
• The discrete p-dispersion problem
• The Euclidean k-supplier problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(5)

• The Euclidean \(k\)-supplier problem in \(\mathbb R^2\)
• On some variants of Euclidean \(k\)-supplier
• Tight FPT approximation for constrained k-center and k-supplier
• The Euclidean \(k\)-supplier problem
• The Euclidean k-supplier problem

This page was built for publication: Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2217474)