Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p

DOI10.1007/978-3-540-73951-7_46MaRDI QIDQ3603555zbMATH OpenOpenAlexFDO

Authors Binay Bhattacharya, Qiaosheng Shi

Publication date 17 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73951-7_46

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Continuous location (90B85)

Recommendations

• Efficient algorithms for the weighted \(k\)-center problem on a real line
• Optimal algorithms for the \(\alpha\)-neighbor \(p\)-center problem
• An optimal approximation algorithm for the rectilinear m-center problem
• On weighted rectilinear 2-center and 3-center problems
• scientific article; zbMATH DE number 34574
• scientific article; zbMATH DE number 1076394
• Generalized \(p\)-center problems: Complexity results and approximation algorithms
• An algorithm and a core set result for the weighted Euclidean one-center problem
• Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance
• A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane

Cited in

(21)

• Rank-two update algorithm versus Frank-Wolfe algorithm with away steps for the weighted Euclidean one-center problem
• Algorithms for finding P-centers on a weighted tree (for relatively small P)
• A linear-time algorithm for the center problem in weighted cycle graphs
• Computing the line-constrained \(k\)-center in the plane for small \(k\)
• Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance
• The weighted \(k\)-center problem in trees for fixed \(k\)
• An \(O(n\log n)\)-time algorithm for the \(k\)-center problem in trees
• The two-center problem of uncertain points on a real line
• An \(O(n\log n)\)-time algorithm for the \(k\)-center problem in trees
• On weighted rectilinear 2-center and 3-center problems
• Fighting terrorism: how to position rapid response teams?
• Linear-time fitting of a \(k\)-step function
• Linear-time fitting of a \(k\)-step function
• A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane
• Efficient algorithms for the weighted \(k\)-center problem on a real line
• Computing the center of uncertain points on tree networks
• An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees
• The \(p\)-center problem in tree networks revisited
• Efficient algorithms for the one-dimensional \(k\)-center problem
• Geometric \(p\)-center problems with centers constrained to two lines
• An algorithm and a core set result for the weighted Euclidean one-center problem

This page was built for publication: Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p

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