\

In the incapacitated facility location problem, we have a set of client's D and a set of facilities F. For each client j Element D and facility i Element F, there is a cost c_ij of assigning client j to facility i. Furthermore, there is a cost f_1, associated with each facility i Element F. The goal of the problem is to choose a subset of facilities F' greaterthanorequalto F so as to minimize the total cost of the facilities in F' and the cost of assigning each client j Element D to the nearest facility in F'. in other words, we wish to find F' so as to minimize sigma_i Element F' f_i + sigma_j Element D min_i Element F'c _ij. Show that there exists some e such that there is no (c in | D |)-approximation algorithm for the incapacitated facility location problem unless P = NP. Give an O(ln |D|)-approximation algorithm for the incapacitated facility location