Directed Steiner Tree and the Lasserre Hierarchy

2011/11/23 by Rothvoß, Thomas · 2 citations
#Data Structures and Algorithms (cs.DS) #F.2.0 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1111.5473

Abstract

The goal for the Directed Steiner Tree problem is to find a minimum cost tree in a directed graph G=(V,E) that connects all terminals X to a given root r. It is well known that modulo a logarithmic factor it suffices to consider acyclic graphs where the nodes are arranged in L <= log |X| levels. Unfortunately the natural LP formulation has a |X|^(1/2) integrality gap already for 5 levels. We show that for every L, the O(L)-round Lasserre Strengthening of this LP has integrality gap O(L log |X|). This provides a polynomial time |X|^epsilon-approximation and a O(log³ |X|) approximation in O(n^log |X|) time, matching the best known approximation guarantee obtained by a greedy algorithm of Charikar et al.

Cited by

• Randomized Rounding over Dynamic Programs
• Planar Length-Constrained Minimum Spanning Trees

Related

• O(log²k/loglogk)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
• On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
• Polynomial Integrality Gap of Flow LP for Directed Steiner Tree
• A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
• An Improved Integrality Gap for Steiner Tree