An optimal approximation algorithm for the rectilinear m-center problem

DOI10.1007/BF01840393zbMATH Open0696.68063MaRDI QIDQ911284FDOQ911284

Authors: N. E. Zubov 

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

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

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)

Cites Work

• Title not available (Why is that?)
• On the rectangularp-center problem
• On the Complexity of Some Common Geometric Location Problems
• Single Facility $l_p $-Distance Minimax Location

Cited In (16)

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

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)