Hi! I am a third year PhD student at the Toyota Technological Institute at Chicago, where I am advised by Prof. Julia Chuzhoy. I am interested in Theoretical Computer Science, mainly Approximation Algorithms and Hardness of Approximation.
Before that, I received my BTech in Computer Science and Engineering from Indian Institute of Technology, Kanpur under the supervision of Prof. Surender Baswana.
In my free time I cook, while trying to optimize the ratio of taste over effort. I try to keep the recipes Gujarati at heart, but cook with convenient ingredients (see the recipe of my staple dinner). When the weather is warm enough I like to read on my hammock, somewhere close to the lake-shore. Also, I am learning sailing these days!
Node-Disjoint Paths (NDP) is a problem where we are given a graph and some source-destination pairs. The goal is to 'route' as many of these pairs of vertices as possible, along paths that don't intersect anywhere. We give an approximation algorithm for a special case of NDP problem: (i) the graph is an undirected grid; and (ii) the sources lie on its boundary.
Node-Disjoint Paths (NDP) is a problem where we are given a graph and some source-destination pairs. The goal is to 'route' as many of these pairs of vertices as possible, along paths that don't intersect anywhere. We show that it is hard to approximate the solution, even when the graph is a grid. The hardness of approximation factor that we achieve is almost polynomial.
Node-Disjoint Paths (NDP) is a problem where we are given a graph and some source-destination pairs. The goal is to 'route' as many of these pairs of vertices as possible, along paths that don't intersect anywhere. We show that it is quite hard to approximate the solution, even when the graph is planar.
Cartoon by Divya.
Based on minimal by orderedlist.