排序方式: 共有2条查询结果,搜索用时 15 毫秒
1
1.
Mohammad Khairul Hasan Hyunwoo Jung Kyung-Yong Chwa 《Journal of Combinatorial Optimization》2008,16(2):155-172
We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c
e
for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d
j
and a set of facilities F⊆V each has nonnegative opening cost f
i
and capacity to serve all client demands. The objective is to open a subset of facilities, say
, to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost
is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in
Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm. 相似文献
2.
Hyunwoo Jung Mohammad Khairul Hasan Kyung-Yong Chwa 《Journal of Combinatorial Optimization》2009,18(3):258-271
In the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c e on the edges, a set of facilities ??V, a set of demands (i.e., clients) $\mathcal{D}\subseteq VIn the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c
e
on the edges, a set of facilities ℱ⊆V, a set of demands (i.e., clients)
D í V\mathcal{D}\subseteq V
, and a parameter M≥1. Each facility i has a nonnegative opening cost f
i
and each client j has d
j
units of demand. Our objective is to open some facilities, say F⊆ℱ, assign each demand j to some open facility i(j)∈F and connect all open facilities using a Steiner tree T such that the total cost, which is
?i ? Ffi+?j ? Ddjci(j)j+M?e ? Tce\sum_{i\in F}f_{i}+\sum_{j\in \mathcal{D}}d_{j}c_{i(j)j}+M\sum_{e\in T}c_{e}
, is minimized.
We present a primal-dual 6.55-approximation algorithm for the ConFL problem which improves the previous primal-dual 8.55-approximation
algorithm given by Swamy and Kumar (Algorithmica 40:245–269, 2004). 相似文献
1