A 3-approximation algorithm for the k-level uncapacitated facility location problem

K.I. Aardal, F.A. Chudak, D.B. Shmoys

    Research output: Contribution to journalArticleAcademicpeer-review

    94 Citations (Scopus)

    Abstract

    In the k-level uncapacitated facility location problem, we have a set of demand points where clients are located. The demand of each client is known. Facilities have to be located at given sites in order to service the clients, and each client is to be serviced by a sequence of k different facilities, each of which belongs to a distinct level. There are no capacity restrictions on the facilities. There is a positive fixed cost of setting up a facility, and a per unit cost of shipping goods between each pair of locations. We assume that these distances are all nonnegative and satisfy the triangle inequality. The problem is to find an assignment of each client to a sequence of k facilities, one at each level, so that the demand of each client is satisfied, for which the sum of the setup costs and the service costs is minimized. We develop a randomized algorithm for the k-level facility location problem that is guaranteed to find a feasible solution of expected cost within a factor of 3 of the optimum cost. The algorithm is a randomized rounding procedure that uses an optimal solution of a linear programming relaxation and its dual to make a random choice of facilities to be opened. We show how this algorithm can be derandomized to yield a 3-approximation algorithm.
    Original languageEnglish
    Pages (from-to)161-167
    JournalInformation Processing Letters
    Volume72
    Issue number5-6
    DOIs
    Publication statusPublished - 1999

    Fingerprint Dive into the research topics of 'A 3-approximation algorithm for the k-level uncapacitated facility location problem'. Together they form a unique fingerprint.

    Cite this