2026-08-17T19:52:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4388 2024-03-06T10:35:00Z ddc:004 open_access

Geometric Avatar Problems Consuegra, Mario E. Narasimhan, Giri Avatar problems choice 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mario E. Consuegra and Giri Narasimhan 2013 Is Part Of LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2013.389 urn:nbn:de:0030-drops-43889 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.389 eng https://creativecommons.org/licenses/by/3.0/legalcode