Approximation Scheme for the Single-Client Capacitated Facility Location Problem With Operational Cost Budget Constraint

We investigate the single-client capacitated facility location problem with operational cost budget constraint. Specifically speaking, we are given a single client with demand, a set of potential facilities with capacities, and a positive integer specifying the operational cost budget. For each open facility, one should pay its opening cost and operational cost. For each open facility to service the client, one should pay the service cost. The objective is to open enough facilities serving the client’s demand and satisfying the capacity and operational cost budget constraints while minimizing the sum of opening and service costs. In this paper, based on dynamic programming and sparse techniques, we derive a fully polynomial time approximation scheme (FPTAS) with violating the operational cost budget constraint at most an arbitrarily small factor or claim that there is no feasible solution.