Recognizing outstanding research by a Master’s student

Ishan Bansal was named a University Finalist for the Alumni Gold Medal for a Master’s student. He worked under the supervision of Professors Chaitanya Swamy and Jochen Koenemann.

After completing his BSc at Chennai Mathematical Institute, Bansal received two scholarships, the William Tutte Postgraduate Scholarship and the David Johnston International Student Entrance Scholarship.

Bansal’s research focused on combinatorial optimization (or discrete optimization, approximation algorithms and network design. “He impressed me with the speed in which he digested new material, and his drive to generate and discuss algorithmic ideas,” said Koenemann, chair of the Department of Combinatorics and Optimization.

Researchers look to efficiently allocate resources like routers and optical fibres to effectively construct and operate critical infrastructure when studying network design problems. Bansal worked on developing approximation algorithms for a class of computationally intractable network design problems guaranteed to be fast and to return provably near-optimal solutions.

In these types of problems, the network’s links have costs and capacities and demand to be routed between certain source-sink nodes. For Bansal’s thesis, he focused on the capacitated survivable network design problem. He needed to find a minimal-cost set of edges that allow routing the given demand feasibly between source and sink nodes.

The capacitated survivable network design problem is known to be among the hardest problems in the field of combinatorial optimization. “Ishan managed to improve the approximation factor of current algorithms by a doubly exponential factor,” said Swamy. “This is an astounding achievement, made all the more impressive by the fact that it was achieved within the short timeline of the Master’s program.”

The algorithms Bansal studies are part of a thriving research area in theoretical computer science and mathematical optimization. He’s continuing his studies in the prestigious PhD program at Cornell’s School of Operations Research and Industrial Engineering.

Bansal will receive a certificate for his work. He is one of five outstanding students from various faculties who represent our exceptionally gifted community of graduate scholars who are creating knowledge and generating transformative research for the betterment of society.