# Invited Talk by Dr. R Inkulu on A polynomial time algorithm for finding an approximate shortest path amid weighted regions

**T**

**itle:**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