Design and analysis of LP-based approximation algorithms for facility location problems

Abstract

Design and analysis of approximation algorithms for facility location problems has been an active area of research in operations research, theory of computation, and telecommunication network for the past decade. Facility location problem (FLP) starts with clients and facilities given. Each facility has facility opening cost. The objective of an FLP is to open a subset of facilities and connect each client to an open facility so that the sum of connection cost and facility opening cost is minimized. Most of the facility location problems that we deal with in this thesis are NP-hard problems. We focus on approximation algorithms that guarantee a solution within constant factor times the value of an optimal solution for FLPs. In approximation algorithms, it is crucial to get a tight lower bound in polynomial time, for it helps reducing an approximation factor. Then, we construct a solution that guarantees a constant factor approximation from the lower bound. We use two types of methods, namely, LP-based and non-LP-based in our approximation algorithms. An LP-solution is known to provide a lower bound for an optimal cost. We present LP-based improved approximation algorithms on connected facility location, hybrid wireless facility location, priority facility location, and facility location with service installation costs, all of which have LP-formulations. In detail, we use primal-dual methods for connected facility location problem and hybrid wireless facility location that require connection of open facilities via a Steiner tree. For priority facility location and facility location with service installation costs whose clients need services, we use a randomized algorithm that combines an LP-solution and a bi-factor solution. By using non-LP-based methods, we present approximate and exact algorithms on online facility location, minimum diameter Steiner tree, and quake detector location that need aggregation of clients for solving the problems. We improve either...