Integrated Logistics: Approximation Algorithms Combining Facility Location and Network Design

摘要

We initiate a study of the approximability of integrated logistics problems that combine elements of facility location and the associated transport network design. In the simplest version, we are given a graph G = (V, E) with metric edge costs c, a set of potential facilities F is concontained in V with nonnegative facility opening costs Φ, a set of clients D is contained in V (each with unit demand), and a positive integer u (cable capacity). We wish to open facilities and construct a network of cables, such that every client is served by some open facility and all cable capacities are obeyed. The objective is to minimize the sum of facility opening and cable installation costs. With only one zero-cost facility and infinite u, this is the Steiner tree problem, while with unit capacity cables this is the Uncapacitated Facility Location problem. We give a (ρST + ρU FL)-approximation algorithm for this problem, where ρP denotes any approximation ratio for problem P. For an extension when the facilities don't have costs but no more than p facilities may be opened, we provide a bicriteria approximation algorithm that has total cost at most ρp-MEDIAN + 2 times the minimum but opens up to 2p facilities. Finally, for the general version with k different types of cables, we extend the techniques of [Guha, Meyerson, Munagala, STOC 2001] to provide an O(k) approximation.