Minimum Cost Source Location Problems with Flow Requirements |
| |
Authors: | Mariko Sakashita Kazuhisa Makino Satoru Fujishige |
| |
Affiliation: | (1) Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan;(2) Graduate School of Information Science and Technology, University of Tokyo, Tokyo 113-8656, Japan;(3) Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan |
| |
Abstract: | In this paper, we consider source location problems and their generalizations with three connectivity requirements (arc-connectivity
requirements λ and two kinds of vertex-connectivity requirements κ and
), where the source location problems are to find a minimum-cost set S⊆V in a given graph G=(V,A) with a capacity function u:A→ℝ+ such that for each vertex v∈V, the connectivity from S to v (resp., from v to S) is at least a given demand d
−(v) (resp., d
+(v)). We show that the source location problem with edge-connectivity requirements in undirected networks is strongly NP-hard,
which solves an open problem posed by Arata et al. (J. Algorithms 42: 54–68, 2002). Moreover, we show that the source location problems with three connectivity requirements are inapproximable within a ratio
of cln D for some constant c, unless every problem in NP has an O(N
log log N
)-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.
By the inapproximable results above, this implies that all the source location problems are Θ(ln ∑
v∈V
(d
+(v)+d
−(v)))-approximable.
An extended abstract of this paper appeared in Sakashita et al. (Proceedings of LATIN 2006, Chile, LNCS, vol. 3887, pp. 769–780, March 2006). |
| |
Keywords: | Connectivity Location problem Combinatorial optimization Approximation algorithm |
本文献已被 SpringerLink 等数据库收录! |
|