Abstract:

Traditionally, we assume that all the clients to be provided service in the facility location problems. In our study, we explore the case when only a fraction of clients allow to be denied service in the final solution. Indeed, the existence of outliers will not only increase the total cost, but also have an undesirable effect on the service quality of other clients. We consider the squared metric facility location problem with outliers, which is a generalization of the classic uncapacitated facility location problem. Next we will give a detailed description of the problem. Given a set of facilities with open cost and a set of clients with connection costs, we seek a subset of facilities to open and satisfy the demands of clients. The objective is to minimize the sum of total open and connection cost. We utilize the primal-dual scheme to design an approximation algorithm, and prove that the proposed algorithm is a 9-approximation.

Key words: outliers, facility location, approximation algorithm, primal-dual scheme, NP-Hard