Minimum cost source location problems with flow requirements

DOI10.1007/s00453-007-9012-yzbMath1134.90435MaRDI QIDQ2482728

Kazuhisa Makino, Satoru Fujishige, Mariko Sakashita

Publication date: 23 April 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9012-y

zbMATH Keywords

Combinatorial optimization; Approximation algorithm; Connectivity; Location problem

Mathematics Subject Classification ID

90C27: Combinatorial optimization

90B80: Discrete location and assignment

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum cost source location problem with vertex-connectivity requirements in digraphs
• An algorithm for source location in directed graphs
• An analysis of the greedy algorithm for the submodular set covering problem
• The source location problem with local 3-vertex-connectivity requirements
• Locating Sources to Meet Flow Demands in Undirected Networks
• Simultaneous source location
• A threshold of ln n for approximating set cover
• Minimum Cost Source Location Problems with Flow Requirements
• On the hardness of approximating minimization problems
• Source location problems considering vertex-connectivity and edge-connectivity simultaneously
• Transversals of subtree hypergraphs and the source location problem in digraphs
• Algorithms and Computation