BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/97
DTSTAMP:20230914T125910Z
SUMMARY:A Near-tight Approximation Algorithm for the Robot Localization Pro
blem
DESCRIPTION:Speaker: Apurva Mudgal\nIndian Institute of Technology\, Ropar\
nDepartment of Computer Science and\nEngineering\nNangal Roa\n\nAbstract:
\nLocalization is a fundamental problem in robotics. The kidnapped robot
possesses a compass and map of its environment it must determine its loc
ation at a minimum cost of travel distance. The problem is NP-hard even t
o minimize within factor $c\\\\log n$\, where $n$ is the map size. No effi
cient approximation algorithm is known.\n\nWe give an $O(\\\\log3 n)$-fact
or algorithm which runs in polynomial time. The key idea is to plan travel
in a ``majority-rule'' map\, which eliminates uncertainty and permits a l
ink to the $\\\\frac{1}{2}$-Group Steiner (not Group Steiner) problem. Th
e approximation factor is not far from optimal: we prove a $c\\\\log^{2-\\
\\epsilon} n$ lower bound\, assuming $NP \\\\not\\\\subseteq ZTIME(n^{poly
log(n)})$\, for the grid graphs commonly used in practice. We also extend
the algorithm to polygonal maps by discretizing the problem using novel ge
ometric techniques.\n
URL:https://www.tcs.tifr.res.in/web/events/97
DTSTART;VALUE=DATE:20100628
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR