@inproceedings{6f2b8ad8792a4ccba352bf5614bc711d,
title = "Linear programming hierarchies suffice for directed steiner tree",
abstract = "We demonstrate that ℓ rounds of the Sherali-Adams hierarchy and 2ℓ rounds of the Lov{\'a}sz-Schrijver hierarchy suffice to reduce the integrality gap of a natural LP relaxation for Directed Steiner Tree in ℓ-layered graphs from ω (√k) to O(ℓ·logk) 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(ℓ·logk). We also observe that Directed Steiner Tree instances with 3 layers of edges have only an O(logk) integrality gap in the standard LP relaxation, complementing the known fact that the gap can be as large as ω (√k) in graphs with 4 layers.",
author = "Zachary Friggstad and Jochen K{\"o}nemann and Young Kun-Ko and Anand Louis and Mohammad Shadravan and Madhur Tulsiani",
year = "2014",
doi = "10.1007/978-3-319-07557-0_24",
language = "English (US)",
isbn = "9783319075563",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "285--296",
booktitle = "Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Proceedings",
address = "Germany",
note = "17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014 ; Conference date: 23-06-2014 Through 25-06-2014",
}