Improved complexity results for several multifacility location problems on trees

DOI10.1007/s10479-011-0905-4zbMath1233.90212MaRDI QIDQ763099

Jörg Kalcsics

Publication date: 9 March 2012

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-011-0905-4

zbMATH Keywords

dynamic programming; tree networks; ordered median problem; multifacility location problems

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B80: Discrete location and assignment

Related Items

Revisiting \(k\)-sum optimization, Fair optimization and networks: a survey

Cites Work

• On the exponential cardinality of FDS for the ordered \(p\)-median problem
• Improved complexity bounds for location problems on the real line
• Algorithmic results for ordered median problems
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Location Theory
• New Results on the Complexity of p-Centre Problems
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• A polynomial algorithm for thep-centdian problem on a tree
• Slowing down sorting networks to obtain faster sorting algorithms
• Multifacility ordered median problems on networks: A further analysis
• The \(k\)-centrum multi-facility location problem
• Unnamed Item
• Unnamed Item