Authors: | Lammersen, Christiane |
Title: | Approximation Techniques for Facility Location and Their Applications in Metric Embeddings |
Language (ISO): | en |
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. |
Subject Headings: | facility location clustering embedding approximation algorithms streaming algorithms distributed algorithms kinetic data structures |
URI: | http://hdl.handle.net/2003/27597 http://dx.doi.org/10.17877/DE290R-8506 |
Issue Date: | 2011-02-01 |
Appears in Collections: | LS 02 Komplexitätstheorie und Effiziente Algorithmen |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Thesis_Lammersen_Christiane.pdf | DNB | 2.46 MB | Adobe PDF | View/Open |
This item is protected by original copyright |
This item is protected by original copyright rightsstatements.org