Tata Institute of Fundamental Research
Half-integral Duals, Connectivity Augmentation and Multiflows in Planar Graphs
STCS Seminar
Speaker:
Naveen Garg (Computer Science and Engineering
Indian Institute of Technology Delhi
New Delhi)
Organiser:
Rahul Vaze
Date:
Tuesday, 23 Jun 2020, 14:00 to 15:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: 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)
| Speaker: | Naveen Garg (Computer Science and Engineering Indian Institute of Technology Delhi New Delhi) |
| Organiser: | Rahul Vaze |
| Date: | Tuesday, 23 Jun 2020, 14:00 to 15:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: 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)
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)