Hard cases of the multifacility location problem

DOI10.1016/j.dam.2003.05.005zbMath1077.90036OpenAlexW2070761038MaRDI QIDQ1887076

Alexander V. Karzanov

Publication date: 23 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2003.05.005

zbMATH Keywords

Location problemMetric extensionModulargraphMultiterminal (multiway) cut

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80) Distance in graphs (05C12)

Related Items

One more well-solved case of the multifacility location problem ⋮ Unnamed Item ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ Minimum 0-extension problems on directed metrics

Cites Work

• Networks with Condorcet solutions
• Minimum 0-extensions of graph metrics
• A characterization of minimizable metrics in the multifacility location problem
• Minimum \((2,r)\)-metrics and integer multiflows
• A multifacility location problem on median spaces
• One more well-solved case of the multifacility location problem
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
• The Complexity of Multiterminal Cuts