Invited Talk by Dr. R Inkulu on A polynomial time algorithm for finding an approximate shortest path amid weighted regions
Title: A polynomial time algorithm for finding an approximate shortest path amid weighted regions
Speaker: Dr. R Inkulu, IIT Guwahati
Host Faculty: Dr. Subrahmanyam Kalyanasundaram
Room No: Room 317 in academic block A.
This talk is on a polynomial-time approximation scheme for the classical geometric problem of finding an approximate short path amid weighted regions. In this problem, a triangulated region P comprising of n vertices, a positive weight associated with each triangle, and two points s and t that belong to P are given as the input. The objective is to find a path whose cost is at most (1 + \epsilon)OPT, where OPT is the cost of an optimal path between s and t. The proposed result is about a cubic factor (in n) improvement over the Mitchell and Papadimitriou ’91 result, which is the only known polynomial time algorithm for this problem to date; for these twenty five years, several pseuo-polynomial time algorithms were proposed. Our algorithm progresses a discretized-Dijkstra wavefront in controlled fashion from source s to achieve this improvement. Further, with polynomial time preprocessing of P, a map is computed which allows answering single-source approximate weighted shortest path queries in polynomial time. (This is Dr. Inkulu’s joint work with Prof. Sanjiv Kapoor, and is under review.)
Dr. Inkulu is an Associate Professor in the department of Computer Science & Engineering at IIT Guwahati. After doing a Masters at IIT Kharagpur, Dr. Inkulu worked for 6+ years in software industry (1.5 years in India and 4.5+ years in USA) prior to joining for PhD at IIT Chicago. After graduating with PhD, he worked as a postdoc at UT-Austin for 2+ years. Thereafter he joined IIT Guwahati. The research interests of Inkulu are in designing (approximation) algorithms to optimization problems in computational geometry.
Monday, December 4, 2017 - 11:00