An Approximation Algorithm For The κ-Level Capacitated Facility Location Problem

This thesis considers the k-level capacitated facility location problem (k-CFLP).The k-CFLP is NP-hard and unifies several existing facility location problems which have been studied from approximation algorithm points of view, such as the uncapacitated facility location problem (UFLP), the 1-level capacitated facility location problem (1-CFLP) and the k-level uncapacitated facility location problem (k-FLP). In this thesis, we introduce the multiexchange local search algorithm(MLS) and LP-based approximation algorithm for the 1-CFLP; we also introduce the parameterized path reduction and greedy algorithm, the split and recursive path algorithm and the randomized rounding algorithm for the k-FLP.In this thesis, we present a combinatorial approximation algorithm for the k-CFLP. At the process of algorithm design, firstly, for any instance M of the k-CFLP, we define an instance M_k-1 of (k-1)-CFLP and an instance S of 1-CFLP;secondly, solve S by the MLS algorithm to obtain a feasible solution for S, solve M_k-1 recursively to obtain a feasible solution for M_k-1;thirdly, for each client j∈D construct a transportation problem, by solving this problem, we see how to transfer the demand from the first level to the path set; finally, construct a solution for instance M. At the process of algorithm analysis, we apply the recursive method and obtain the first (combinatorial) approximation algorithmwith a performance factor of k+2+(?)+ε(ε>0) for this problem.