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