We study the Connected Facility Location problems. We are given a connected graph G = (V,E) with non-negative edge cost $C_e$ for each edge $e\inE$, a set of clients D⊆V such that each client $j\inD$ has positive demand $d_j$ and a set of facilities F⊆V each has non-negative opening cost $f_i$ and capacity to serve all client demands. The objective is to open a subset of facilities, say $\hat{F}$, connect each client $j\inD$ to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost $\sum_{i\in \hat{F}}f_i + \sum_{j\in D}d_jc_{i(j)j} + M\sum_{e\in T}c_e$ is minimized, where M ≥1 be an input parameter. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55. We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.
이 논문은 연결 시설 배치 문제에 대한 연구이다. 우리는 연결된 가중치 그래프 G = (V, E)와 양수의 edge값, 사용자들의 집합 D과 각 사용자는 양수의 요구사항을 가지며, 시설의 집합 V와 각 시설들은 양수의 개시 비용과 모든 사용자들에게 서비스하기 위한 용량을 가지는 문제를 제시한다. 이 논문의 목적은 각 사용자들이 하나의 개시된 시설에 연결되고, 모든 개시된 시설들은 개시된 모든 시설들을 연결하는 Steiner tree T로 연결되어 있으며, 모든 사용자들의 요구를 수용하는 시설의 개시비용과 사용자들의 시설 연결 비용, 사용자 요구 처리 비용을 최소화한 시설의 부분집합을 찾는 것이다. 여기서 사용자 요구 처리 비용은 사용자의 요구와 사용자와 시설의 최소 연결 비용의 곱이며, 시설 연결 비용은 M과 Steiner tree의 구성비용의 곱이고, M은 1 이상의 사용자의 입력 값이다. 이 논문은 Linear Programming-Rounding 기법에 기반한 8.29 근사 알고리즘을 제시한다. 이것은 기존의 8.55 근사 알고리즘보다 향상된 것이며, 모든 시설의 개시 비용이 동일할 때 7.0 근사 알고리즘을 제시한다. 이들 알고리즘은 먼저 relaxed 문제의 부분 최적 해를 구하고, filtering과 rounding을 사용하여 정수 해를 구한다.
