Question

set_cover
facility_location

In the uncapacitated facility location problem, we have a set of clients DD and a set of facilities FF. For each client jDj \in D and facility iFi \in F, there is a cost cijc_{ij} of assigning client jj to facility ii. Furthermore, there is a cost fif_i associated with each facility iFi \in F. The goal of the problem is to choose a subset of facilities FFF' \subseteq F so as to minimize the total cost of the facilities in FF' and the cost of assigning each client jDj \in D to the nearest facility in FF'. In other words, we wish to find FF' so as to minimize iFfi+jDminiFcij\sum_{i \in F'} f_i + \sum_{j \in D}\min_{i \in F}c_{ij}.

  1. Show that there exists some cc such that there is no (clnD)(c \ln |D|)-approximation algorithm for the uncapacitated facility location problem unless P = NP.
  2. Give an O(lnD)O(\ln |D|)-approximation algorithm for the uncapacitated facility location problem.
1

Answers

1. We show an approximation preserving reduction from the set cover problem:

Given an instance of the set cover problem (E,S)(E, \mathcal{S}) we create the following instance of the facility location problem:(E,S)(E, \mathcal{S}) and set

cij={0if  iSj1otherwise c_{ij} = \begin{cases} 0 & \text{if}\; i \in S_j \\ 1 & \text{otherwise} \end{cases}

We also set fif_i to be 1 for each ii.Clearly every solution to the facility location can be transformed to a solution to the set cover problem of the same price and vice versa.

2. We now formalize the facility location problem as a set cover problem. In this formulation there will be an exponential number of sets but we will argue that we can use the greedy algorithm for this instance of set cover in polynomial time.

Given a facility location instance (F,D,c,f)(F, D, c, f) we define the following set cover instance (S,D,w)(\mathcal{S}, D, w) where S=F×2D\mathcal{S} = F \times 2^D. We let the set (i,DD)S(i, D' \subseteq D) \in \mathcal{S} covers the elements of DD' and define its cost to be fi+jDcijf_i + \sum_{j \in D}c_{ij}.

Clearly an optimal solution to the above set cover instance is an optimal solution to the corresponded facility location instance.

Now we argue that, in each iteration, we can find the set that minimizes the cost per element in polynomial time. For two number k[F]k \in [|F|] and l[D]l \in [|D|] let the set corresponded to kk and ll be (k,D)(k, D') where DD' are the ll clients closest to facility kk there are klkl such sets that can be found in polynomial time and one can convinced himself that the set that minimizes the cost per uncovered client is among those sets. Thus we have a O(lnD)O(\ln D)-approximation algorithm for the facility location problem.

1
Feedback