New algorithms for facility location problems on the real line

DOI10.1007/s00453-012-9737-0zbMath1360.90156OpenAlexW1977108333MaRDI QIDQ517797

Danny Z. Chen, Haitao Wang

Publication date: 27 March 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9737-0

zbMATH Keywords

facility locationalgorithm analysis\(k\)-medianreal linealgorithm design\(k\)-coverage

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Continuous location (90B85)

Related Items

The Coverage Problem by Aligned Disks, The coverage problem by aligned disks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved algorithms for path partition and related problems
• Algebraic optimization: The Fermat-Weber location problem
• A linear-time algorithm for concave one-dimensional dynamic programming
• Geometric complexity of some location problems
• Geometric applications of a matrix-searching algorithm
• Improved complexity bounds for location problems on the real line
• Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications
• Monge strikes again: Optimal placement of web proxies in the internet
• The Maximum Coverage Location Problem
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• The concave least-weight subsequence problem revisited
• Note—One-Dimensional Facility Location-Allocation using Dynamic Programming
• Computing a Minimum Weightk-Link Path in Graphs with the Concave Monge Property
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
• New Algorithms for 1-D Facility Location and Path Equipartition Problems
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• On the p‐coverage problem on the real line