Approximation Techniques for Facility Location and Their Applications in Metric Embeddings

Abstract

This thesis addresses the development of geometric approximation algorithms for huge datasets and is subdivided into two parts. The first part deals with algorithms for facility location problems, and the second part is concerned with the problem of computing compact representations of finite metric spaces. Facility location problems belong to the most studied problems in combinatorial optimization and operations research. In the facility location variants considered in this thesis, the input consists of a set of points where each point is a client as well as a potential location for a facility. Each client has to be served by a facility. However, connecting a client incurs connection costs, and opening or maintaining a facility causes so-called opening costs. The goal is to open a subset of the input points as facilities such that the total cost of the system is minimized.