License
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://drops.dagstuhl.de/opus/volltexte/2013/4388/
Go to the corresponding LIPIcs Volume Portal


Consuegra, Mario E. ; Narasimhan, Giri

Geometric Avatar Problems

pdf-format:
29.pdf (0.5 MB)


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
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 09.12.2013


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI