Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

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)
What and Who
Title:Half-integral Duals, Connectivity Augmentation and Multiflows in Planar Graphs
Speaker:Naveen Garg
coming from:Indian Institute of Technology Delhi
Speakers Bio: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.
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D3, D4, RG1, MMCI, D2, INET, D5, SWS
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Friday, 21 February 2020
Duration:30 Minutes
Building: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)

Name(s):Naveen Garg
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Keywords:Approximation algorithms, Flows, Connectivity, Planar Graphs
Attachments, File(s):
  • Naveen Garg, 01/28/2020 03:51 AM -- Created document.