Lasserre Integrality Gaps for Graph Spanners and Related Problems

05/17/2019
by   Michael Dinitz, et al.
0

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 in a variety of settings. 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset