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

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    94 Citaten (Scopus)

    Samenvatting

    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.
    Originele taal-2Engels
    Pagina's (van-tot)161-167
    TijdschriftInformation Processing Letters
    Volume72
    Nummer van het tijdschrift5-6
    DOI's
    StatusGepubliceerd - 1999

    Vingerafdruk Duik in de onderzoeksthema's van 'A 3-approximation algorithm for the k-level uncapacitated facility location problem'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit