Campus Event Calendar

Event Entry

What and Who

Half-integral Duals, Connectivity Augmentation and Multiflows in Planar Graphs

Naveen Garg
Indian Institute of Technology Delhi
AG1 Mittagsseminar (own work)

Naveen is with the CSE department at IIT Delhi. Prior to joining IITD he was a postdoc at MPII (1994-97). He is interested in algorithms in general, and approximation, online and game theoretic algorithms in particular.
AG 1, AG 3, AG 4, RG1, MMCI, AG 2, INET, AG 5, SWS  
AG Audience

Date, Time and Location

Friday, 21 February 2020
30 Minutes
E1 4


Given an edge weighted graph and a spanning tree, $T$, the {\em tree augmentation problem} is to pick a minimum weight set of edges, $F$, such that $T\cup F$ is 2-edge connected. Williamson gave a 2-approximation algorithm for this problem using the primal-dual schema. We show that when edge weights are integral, the WGMV procedure can be modified to obtain a half-integral dual.
The tree augmentation problem has an interesting connection to routing flow in graphs where the union of supply and demand is planar. The half-integrality of the dual leads to a tight 2-approximate max-half-integral-flow min-multicut theorem and a 4-approximate max-integral flow min-multicut theorem.
(joint work with Nikhil Kumar and Andras Sebo)


Naveen Garg
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Approximation algorithms, Flows, Connectivity, Planar Graphs

Naveen Garg, 01/28/2020 03:51 -- Created document.