Open Collections

Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation for Two-connected Directed Steiner Tree

Banff International Research Station for Mathematical Innovation and Discovery

Joint work with Bundit Laekhanukit The high-level goal of survivable network design is to design cheap networks that satisfy giving connectivity requirements even in the preserve of node or edge faults. While many approximation algorithms are known for a variety of such problems in undirected graphs, not much is known for directed ones. In this work we present the first non-trivial approximation algorithm for the 2-edge connectivity generalization of Directed Steiner Tree (DST). Analogously to DST, our approach gives a polylogarithmic approximation in quasi-polynomial time, or an $n^{\epsilon}$ approximation in polynomial time. Our approach is based on a complex LP-rounding algorithm that combines the notion of divergent trees and Zelikosky’s height reduction via a probabilistic mapping.

Mathematics; Computer science; Operations research, mathematical programming; Theoretical computer science

video/mp4

Author affiliation: IDSIA, University of Lugano

2018-05-14

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/65839

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/