Minimum Cost Source Location Problems with Flow Requirements.

In this paper, we consider source location problems and their generalizations with three connectivity requirements λ, κ and . We show that the source location problem with edge-connectivity requirement λ in undirected networks is strongly NP-hard, and that no source location problems with three connectivity requirements in undirected/directed networks are approximable within a ratio of , unless NP has an -time deterministic algorithm. Here D denotes the sum of given demands. We also devise (1+ln D)-approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions. Furthermore, we study the extended source location problems when a given graph is a tree. Our algorithms for all the extended source location problems run in pseudo-polynomial time and the ones for the source location problem with vertex-connectivity requirements κ and run in polynomial time, where pseudo-polynomiality for the source location problem with the arc-connectivity requirement λ is best possible unless P=NP, since it is known to be weakly NP-hard, even if a given graph is a tree. Keywords: Connectivity, location problem, combinatorial optimization, and approximation algorithm. [ABSTRACT FROM AUTHOR]