Archimedes Talk on "Seymour instances, half-integral flows and uncrossable cut-cover" by Prof. Naveen Garg(Indian Institute of Technology (IIT), Delhi)

Abstract: 

The cut condition is necessary and sufficient for routing of multicommodity flow when the union of the supply and demand graph is planar; such instances are called Seymour instances. We consider the problem of maximizing ½-integral flow and provide a tight relation with integer multicut in such instances. To do so we prove that the primal-dual algorithm of Williamson et.al. for finding a minimum cover of uncrossable set functions can be modified to obtain a half-integral dual.

Short Biography:

Naveen Garg is the Usha Hasteer Professor of Computer Science at the Indian Institute of Technology Delhi. He did his B.Tech. and Ph.D. in Computer Science from IIT Delhi, was a postdoctoral researcher at the Max-Planck-Institut fur Informatik, Germany and since 1998 he has been a faculty member at IIT Delhi. Naveen’s contributions are primarily in the design and analysis of approximation algorithms for NP-hard combinatorial optimization problems arising in network design, scheduling, routing, facility location etc. He is a Fellow of Indian Academy of Science, and the Indian National Academy of Engineering and was awarded the SS Bhatnagar award for Mathematical Sciences in 2016.

Online participants: MS-Teams, https://teams.microsoft.com/meet/321692915270971?p=VWkGMiyxlYinN7Mt0o