Directed Steiner Tree and the Lasserre Hierarchy

Details Directed Steiner Tree and the Lasserre Hierarchy Directed Steiner Tree and the Lasserre Hierarchy

2011-11-23

arxiv.org/abs/1111.5473v1

Computer Science

Data Structures and Algorithms

23 pages, 1 figure

Scientific paper

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^3 |X|) approximation in O(n^{log |X|) time, matching the best known approximation guarantee obtained by a greedy algorithm of Charikar et al.

Affiliated with

Also associated with

No associations

Rating

Directed Steiner Tree and the Lasserre Hierarchy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Directed Steiner Tree and the Lasserre Hierarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Directed Steiner Tree and the Lasserre Hierarchy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-377190