max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Half-integral Duals, Connectivity Augmentation and Multiflows in Planar Graphs Naveen Garg Indian Institute of Technology Delhi 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. AG1 Mittagsseminar (own work) D1, D3, D4, RG1, MMCI, D2, INET, D5, SWSWe use this to send out email in the morning. AG Audience English
Date: Friday, 21 February 2020 13:00 30 Minutes Saarbrücken E1 4 024
 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 et.al. 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)
Name(s): Naveen Garg --email address not disclosed on the web