On weighted rectilinear 2-center and 3-center problems

DOI10.1016/0020-0255(91)90050-5MaRDI QIDQ757236zbMATH OpenOpenAlexFDO

Authors R. C. T. Lee, Ming-Tat Ko

Publication date 1991

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0255(91)90050-5

zbMATH Keywords

weighted rectilinear m-center optimization

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Continuous location (90B85) Abstract computational complexity for mathematical programming problems (90C60)

Review text

The authors consider the weighted rectilinear m-center optimization problem: given n demand points with positive weights, find m service points on the plane so as to minimize the maximum of the weighted rectilinear distances from the given demand points to their respective nearest service points. A number r is said to be feasible if there exists a set C of m service points such that the value of the objective function at C is less than or equal to r. For any \(r>0\), the weighted m-center decision problem consists in determining whether r is feasible. For \(m=2\) and \(m=3\), the authors propose O(n) algorithms for solving the corresponding decision problems. Then these algorithms are used to construct methods with time complexity O(n log n) for solving the m-center optimization problems corresponding to \(m=2\) and \(m=3\).

Recommendations

• On the rectangularp-center problem
• scientific article; zbMATH DE number 34574
• An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees
• Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p
• The Weighted Euclidean 1-Center Problem

Cites work

• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• scientific article; zbMATH DE number 3365044 (Why is no real title available?)
• Layout of facilities with some fixed points
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• On the rectangularp-center problem
• Rectilinear m -Center problem
• Single Facility l_p -Distance Minimax Location
• The p-Centre Problem-Heuristic and Optimal Algorithms

Cited in

(12)

• A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane
• Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance
• On weighted centers for semidefinite programming
• A simple linear algorithm for computing rectilinear 3-centers
• scientific article; zbMATH DE number 1588326 (Why is no real title available?)
• scientific article; zbMATH DE number 1728311 (Why is no real title available?)
• Geometric p-center problems with centers constrained to two lines
• Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p
• scientific article; zbMATH DE number 34574 (Why is no real title available?)
• Solving LP Problems via Weighted Centers
• An optimal approximation algorithm for the rectilinear m-center problem
• A note on the m-center problem with rectilinear distances

This page was built for publication: On weighted rectilinear 2-center and 3-center problems

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