Approximation Techniques for Facility Location and Their Applications in Metric Embeddings
Loading...
Date
2011-02-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Table of contents
Keywords
facility location, clustering, embedding, approximation algorithms, streaming algorithms, distributed algorithms, kinetic data structures