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.
Time: 11:00

Abstract:

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.)

Speaker’s Bio:

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.

Dates:
Monday, December 4, 2017 - 11:00