We demonstrate that ℓ rounds of the Sherali-Adams hierarchy and 2ℓ rounds of the Lovasz-Schrijver hierarchy suffice to reduce the integrality gap of a natural LP relaxation for Directed Steiner Tree in ℓ-layered graphs from Ω(k~(1/2)) to O(ℓ·log k) where k is the number of terminals. This is an improvement over Rothvoss' result that 2ℓ rounds of the considerably stronger Lasserre SDP hierarchy reduce the integrality gap of a similar formulation to O(ℓ·log k). We also observe that Directed Steiner Tree instances with 3 layers of edges have only an O(log k) integrality gap in the standard LP relaxation, complementing the known fact that the gap can be as large as Ω(k~(1/2)) in graphs with 4 layers.
展开▼
