TY - GEN
T1 - Lasserre Integrality Gaps for Graph Spanners and Related Problems
AU - Dinitz, Michael
AU - Nazari, Yasamin
AU - Zhang, Zeyu
PY - 2021
Y1 - 2021
N2 - There has been significant recent progress on algorithms for approximating graph spanners, i.e., algorithms which approximate the best spanner for a given input graph. Essentially all of these algorithms use the same basic LP relaxation, so a variety of papers have studied the limitations of this approach and proved integrality gaps for this LP. We extend these results by showing that even the strongest lift-and-project methods cannot help significantly, by proving polynomial integrality gaps even for nΩ ( ε ) levels of the Lasserre hierarchy, for both the directed and undirected spanner problems. We also extend these integrality gaps to related problems, notably Directed Steiner Network and Shallow-Light Steiner Network.
AB - There has been significant recent progress on algorithms for approximating graph spanners, i.e., algorithms which approximate the best spanner for a given input graph. Essentially all of these algorithms use the same basic LP relaxation, so a variety of papers have studied the limitations of this approach and proved integrality gaps for this LP. We extend these results by showing that even the strongest lift-and-project methods cannot help significantly, by proving polynomial integrality gaps even for nΩ ( ε ) levels of the Lasserre hierarchy, for both the directed and undirected spanner problems. We also extend these integrality gaps to related problems, notably Directed Steiner Network and Shallow-Light Steiner Network.
UR - https://www.scopus.com/pages/publications/85112323136
UR - https://www.scopus.com/inward/citedby.url?scp=85112323136&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-80879-2_7
DO - 10.1007/978-3-030-80879-2_7
M3 - Conference contribution
SN - 9783030808785
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 97
EP - 112
BT - Approximation and Online Algorithms
A2 - Kaklamanis, Christos
A2 - Levin, Asaf
PB - Springer Science and Business Media Deutschland GmbH
T2 - 18th International Workshop on Approximation and Online Algorithms, WAOA 2019
Y2 - 9 September 2020 through 10 September 2020
ER -