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
approximation algorithms
streaming algorithms
distributed algorithms
kinetic data structures
Issue Date: 2011-02-01
Appears in Collections:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Files in This Item:
File Description SizeFormat 
Thesis_Lammersen_Christiane.pdfDNB2.46 MBAdobe PDFView/Open

This item is protected by original copyright

All resources in the repository are protected by copyright.