Lasserre Integrality Gaps for Graph Spanners and Related Problems

DOI10.1007/978-3-030-80879-2_7MaRDI QIDQ6318936arXivFDO

Authors Michael Dinitz, Yasamin Nazari, Ze Yu Zhang

Publication date 17 May 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-80879-2_7

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

arXiv classification

cs.CCcs.DSmath.OC

Abstract: 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^{Omega(epsilon)}$ 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.

This page was built for publication: Lasserre Integrality Gaps for Graph Spanners and Related Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6318936)