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)

zbMATH Keywords

approximation algorithmNP-completenessrectilinear m-center problem

Mathematics Subject Classification ID

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

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)

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