Structured \(p\)-facility location problems on the line solvable in polynomial time

DOI10.1016/S0167-6377(97)00035-7zbMath0892.90119OpenAlexW2055836554MaRDI QIDQ1382805

Timothy J. Lowe, Arie Tamir, Vernon Ning Hsu

Publication date: 18 March 1998

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(97)00035-7

zbMATH Keywords

backloggingeconomic lot-sizing\(p\)-facility location

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Inventory, storage, reservoirs (90B05) Dynamic programming (90C39) Discrete location and assignment (90B80)

Related Items (7)

The connected \(p\)-center problem on cactus graphs ⋮ Efficient algorithms for centers and medians in interval and circular-arc graphs ⋮ Approximation algorithms for hard capacitated \(k\)-facility location problems ⋮ An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths ⋮ Multi-depot traveling salesmen location problems on networks with special structure ⋮ The connected \(p\)-center problem on block graphs with forbidden vertices ⋮ The \(k\)-centrum multi-facility location problem

Cites Work

• Unnamed Item
• A linear-time algorithm for concave one-dimensional dynamic programming
• Geometric applications of a matrix-searching algorithm
• Improved complexity bounds for location problems on the real line
• Solving covering problems and the uncapacitated plant location problem on trees
• Sequence comparison with mixed convex and concave costs
• The concave least-weight subsequence problem revisited
• Improved Algorithms for Economic Lot Size Problems

This page was built for publication: Structured \(p\)-facility location problems on the line solvable in polynomial time