One more well-solved case of the multifacility location problem

DOI10.1016/j.disopt.2004.04.001zbMath1087.90064OpenAlexW1993328542MaRDI QIDQ2386213

Alexander V. Karzanov

Publication date: 22 August 2005

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2004.04.001

zbMATH Keywords

Multiterminal cutLocation problemMetric extensionModular graphRetraction of graphs

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Distance in graphs (05C12)

Related Items

Hard cases of the multifacility location problem, Metric packing for \(K_ 3 + K_ 3\), Unnamed Item, Discrete Convex Functions on Graphs and Their Algorithmic Applications, Discrete convexity and polynomial solvability in minimum 0-extension problems, Minimum 0-extension problems on directed metrics, Weakly Modular Graphs and Nonpositive Curvature

Cites Work

• Networks with Condorcet solutions
• Median graphs and Helly hypergraphs
• A combinatorial algorithm for the minimum \((2,r)\)-metric problem and some generalizations
• Minimum 0-extensions of graph metrics
• A characterization of minimizable metrics in the multifacility location problem
• Absolute retracts of bipartite graphs
• Hard cases of the multifacility location problem
• Minimum \((2,r)\)-metrics and integer multiflows
• A multifacility location problem on median spaces
• Combinatorial theory.
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
• The Complexity of Multiterminal Cuts