Assignment Problem in Content Distribution Networks: Unsplittable Hard-Capacitated Facility Location

作者：Bateni Mohammadhossein; Hajiaghayi Mohammadtaghi

来源：ACM Transactions on Algorithms, 2012, 8(3): 20.

DOI：10.1145/2229163.2229164

• Algorithms
• Theory
• Approximation algorithm
• PTAS
• network
• facility location

In a Content Distribution Network (CDN), there are m servers storing the data; each of them has a specific bandwidth. All the requests from a particular client should be assigned to one server because of the routing protocol used. The goal is to minimize the total cost of these assignments-cost of each is proportional to the distance between the client and the server as well as the request size-while the load on each server is kept below its bandwidth limit. When each server also has a setup cost, this is an unsplittable hard-capacitated facility location problem. As much attention as facility location problems have received, there has been no nontrivial approximation algorithm when we have hard capacities (i.e., there can only be one copy of each facility whose capacity cannot be violated) and demands are unsplittable (i.e., all the demand from a client has to be assigned to a single facility). We observe it is NP-hard to approximate the cost to within any bounded factor in this case. Thus, for an arbitrary constant epsilon > 0, we relax the capacities to a 1 + epsilon factor. For the case where capacities are almost uniform, we give a bicriteria O(log n, 1 + epsilon)-approximation algorithm for general metrics and a (1 + epsilon, 1 + epsilon)-approximation algorithm for tree metrics. A bicriteria (alpha, beta)-approximation algorithm produces a solution of cost at most alpha times the optimum, while violating the capacities by no more than a beta factor. We can get the same guarantees for nonuniform capacities if we allow quasipolynomial running time. In our algorithm, some clients guess the facility they are assigned to, and facilities decide the size of the clients they serve. A straightforward approach results in exponential running time. When costs do not satisfy metricity, we show that a 1.5 violation of capacities is necessary to obtain any approximation. It is worth noting that our results generalize bin packing (zero connection costs and facility costs equal to one), knapsack (single facility with all costs being zero), minimum makespan scheduling for related machines (all connection costs being zero), and some facility location problems.

• 出版日期2012-7