License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.389
URN: urn:nbn:de:0030-drops-43889
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4388/
Consuegra, Mario E. ;
Narasimhan, Giri
Geometric Avatar Problems
Abstract
We introduce the concept of Avatar problems that deal with situations where each entity has multiple copies or "avatars" and the solutions are constrained to use exactly one of the avatars. The resulting set of problems show a surprising range of hardness characteristics and elicit a variety of algorithmic solutions. Many Multiple geometric avatar problems are considered. In particular, we show how to extend the concept of epsilon-kernels to find approximation algorithms for geometric avatar problems. Results for metric space graph avatar problems are also presented.
BibTeX - Entry
@InProceedings{consuegra_et_al:LIPIcs:2013:4388,
author = {Mario E. Consuegra and Giri Narasimhan},
title = {{Geometric Avatar Problems}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {389--400},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Anil Seth and Nisheeth K. Vishnoi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4388},
URN = {urn:nbn:de:0030-drops-43889},
doi = {10.4230/LIPIcs.FSTTCS.2013.389},
annote = {Keywords: Avatar problems, choice}
}
|
Keywords: |
|
Avatar problems, choice |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) |
|
Issue Date: |
|
2013 |
|
Date of publication: |
|
10.12.2013 |
