English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Approximation Algorithms for Geometric Optimization Problems

Laue, S. (2008). Approximation Algorithms for Geometric Optimization Problems. PhD Thesis, Universität des Saarlandes, Saarbrücken.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-B591-4 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0028-35D2-F
Genre: Thesis

Files

show Files
hide Files
:
2008_Sören_Laue_Dissertation.pdf (Any fulltext), 664KB
View   Save
File Permalink:
https://hdl.handle.net/11858/00-001M-0000-0027-B593-F
Name:
2008_Sören_Laue_Dissertation.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Laue, Sören1, Author
Funke, Stefan2, Advisor           
Mehlhorn, Kurt2, Referee           
Affiliations:
1International Max Planck Research School, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_1116551              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: This thesis deals with a number of geometric optimization problems which are all NP-hard. The first problem we consider is the set cover problem for polytopes in R3. Here, we are given a set of points in R3 and a fixed set of translates of an arbitrary polytope. We would like to select a subset of the given polytopes such that each input point is covered by at least one polytope and the number of selected polytopes is minimal. By using epsilon-nets, we provide the first constant-factor approximation algorithm for this problem. The second set of problems that we consider are power assignment problems in wireless networks. Ad hoc wireless networks are a priori unstructured in a sense that they lack a predetermined interconnectivity. We consider a number of typical connectivity requirements and either give the first algorithms that compute a (1 + )-approximate energy efficient solution to them, or drastically improve upon existing algorithms in running time. The algorithms are based on coresets. We then extend the algorithms from the Euclidean case to metrics of bounded-doubling dimension and study metric spaces of bounded-doubling dimension more in-depth. The last problem that we consider is the k-hop minimum spanning tree, that is, we are given a graph and a specified root node and we would like to find a minimum spanning tree of the graph such that each root-leaf path contains at most k edges. We give the first PTAS for the problem in the Euclidean plane.

Details

show
hide
Language(s): eng - English
 Dates: 2008-082008
 Publication Status: Issued
 Pages: -
 Publishing info: Saarbrücken : Universität des Saarlandes
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: LauePhd2008
 Degree: PhD

Event

show

Legal Case

show

Project information

show

Source

show