Approximation algorithms for new graph partitioning and facility location problems

Svitkina, Zoya

Approximation algorithms for new graph partitioning and facility location problems

Abstract

In applications as diverse as data placement in peer-to-peer systems, control of epidemic outbreaks, and routing in sensor networks, the fundamental questions can be abstracted as problems in combinatorial optimization. However, many of these problems are NP-hard, which makes it unlikely that exact polynomial-time algorithms for them exist. Approximation algorithms are designed to circumvent this difficulty, by finding provably near-optimal solutions in polynomial time. This thesis introduces a number of new combinatorial optimization problems that arise from various applications and proposes approximation algorithms for them. These problems fall into two general areas: graph partitioning and facility location. The first problem that we introduce is the unbalanced graph cut problem. Here the goal is to find a graph cut, minimizing the size of one of the sides, while also respecting an upper bound on the number of edges cut. We develop two bicriteria approximation algorithms for this problem using the technique of Lagrangian relaxation, and a different algorithm for its maximization version. The other graph partitioning problem that we introduce and study is the min-max multiway cut problem. It aims to partition a graph into multiple components, minimizing the maximum number of edges coming out of any component. We present an approximation algorithm for this problem which uses unbalanced cuts as well as the greedy technique. In the second part of the thesis, we study two generalizations of the facility location problem, which aims to open facilities, assigning clients to them, in order to minimize the facility opening costs and the connection costs. In the facility location with hierarchical facility costs problem, the facility costs are more general, and depend on the set of assigned clients. Our algorithm, based on the local search technique, uses two new local improvement operations, achieving a constant-factor approximation guarantee. The second generalization is the load-balanced facility location problem, which specifies a lower bound for the number of clients assigned to an open facility. We give the first true constant-factor approximation algorithm, which uses a reduction to the capacitated facility location problem. The thesis is concluded with related open problems and directions for future research.

Date Issued

2007-08-03T13:34:47Z

Keywords

approximation; algorithms

Types

dissertation or thesis