Improved complexity results for several multifacility location problems on trees

DOI10.1007/s10479-011-0905-4zbMath1233.90212OpenAlexW1992072336MaRDI 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 programmingtree networksordered median problemmultifacility location problems

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Discrete location and assignment (90B80)

Related Items (2)

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

This page was built for publication: Improved complexity results for several multifacility location problems on trees