A (5.83 + ∈)-Approximation Algorithm for Universal Facility Location Problem with Linear Penalties

摘要

In the universal facility location problem, we are given a set of clients and facilities. Our goal is to find an assignment such that the total connection and facility cost is minimized. The connection cost is proportional to the distance between each client and its assigned facility, whereas the facility cost is a nondecreasing function with respect to the total number of clients assigned to the facility. The universal facility location problem generalizes several classical facility location problems, including the uncapacitated facility location problem and the capacitated facility location problem (both hard and soft capacities). This work considers the universal facility location problem with linear penalties, where each client can be rejected for service with a penalty. The objective is to minimize the total connection, facility and penalty cost. We present a (5.83 + ∈)-approximation local search algorithm for this problem.