Teaching Seminar: How to get from A to B, and other problems

Abstract: Shortest paths in graphs have been studied in computer science for over 60 years. Many different variants of shortest path problems can be solved by well-known, efficient algorithms. However, in most real-world scenarios, the graphs are fixed whereas the edge weights are time-varying. For example, a network of roads doesn't change on a day-to-day basis, but the traffic on the roads varies with time. These problems are highly practical, and also have some applications outside the domain of road networks (like multi-currency arbitrage, financial investment planning). In this talk, we will take an introductory journey into the world of parametric shortest paths, time-dependent shortest paths, and shortest path reconfiguration problems. In the latter part of the talk, we will look at other (unrelated) problems: a rank aggregation problem, a graph labelling problem, and a problem in geometric graphs.

Bio: Kshitij Gajjar completed his Ph.D. in 2019 from the Tata Institute of Fundamental Research, India. The title of his thesis was: "Representing Shortest Paths in Graphs". Since then, he has held postdoc positions at the Technion, Israel, and the National University of Singapore. Presently, he is an Assistant Professor at the Indian Institute of Technology Jodhpur, India. He is interested in algorithms, graph theory, combinatorics, and computational complexity.

https://umass-amherst.zoom.us/j/97587756345?pwd=ZXZ3NjRwY0hNTmxWY29hU2VzNnhQZz09