An optimal approximation algorithm for the rectilinear m-center problem

DOI10.1007/BF01840393MaRDI QIDQ911284zbMATH OpenFDO

Authors N. E. Zubov

Publication date 1990

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01840393

zbMATH Keywords

approximation algorithmNP-completenessrectilinear m-center problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A note on the m-center problem with rectilinear distances
• On the rectangularp-center problem
• Discrete rectilinear 2-center problems
• On weighted rectilinear 2-center and 3-center problems
• A simple linear algorithm for computing rectilinear 3-centers

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the Complexity of Some Common Geometric Location Problems
• On the rectangularp-center problem
• Single Facility l_p -Distance Minimax Location

Cited in

(16)

• Speeding up the optimal method of Drezner for the \(p\)-centre problem in the plane
• Linear-size universal discretization of geometric center-based problems in fixed dimensions
• Parametric search: three new applications
• A linear time deterministic algorithm to find a small subset that approximates the centroid
• A simple linear algorithm for computing rectilinear 3-centers
• One-way and round-trip center location problems
• An efficient algorithm for the Euclidean \(r\)-centrum location problem
• Bounded fan-out \(m\)-center problem
• Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p
• On the rectangularp-center problem
• Rectilinear covering for imprecise input points (extended abstract)
• A Polynomial Time Approximation Scheme for the Closest Shared Center Problem
• Approximation algorithms for a \(k\)-line center
• Approximation algorithms for orthogonal line centers
• A note on the m-center problem with rectilinear distances
• A relaxation-based algorithm for solving the conditional \(p\)-center problem

This page was built for publication: An optimal approximation algorithm for the rectilinear m-center problem

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