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 SizeFormat 
Thesis_Lammersen_Christiane.pdfDNB2.46 MBAdobe PDFView/Open


This item is protected by original copyright



This item is protected by original copyright rightsstatements.org