Lasserre Integrality Gaps for Graph Spanners and Related Problems

Michael Dinitz, Yasamin Nazari, Zeyu Zhang

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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. 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.
Original languageEnglish
Title of host publicationApproximation and Online Algorithms - 18th International Workshop, WAOA 2020, Revised Selected Papers
EditorsC. Kaklamanis, A. Levin
PublisherSpringer Science and Business Media Deutschland GmbH
Pages97-112
ISBN (Print)9783030808785
DOIs
Publication statusPublished - 2021
Externally publishedYes
Event18th International Workshop on Approximation and Online Algorithms, WAOA 2019 - Virtual, Online
Duration: 9 Sept 202010 Sept 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Workshop on Approximation and Online Algorithms, WAOA 2019
CityVirtual, Online
Period9/09/2010/09/20

Funding

Supported in part by NSF award CCF-1909111.

FundersFunder number
National Science FoundationCCF-1909111

    Fingerprint

    Dive into the research topics of 'Lasserre Integrality Gaps for Graph Spanners and Related Problems'. Together they form a unique fingerprint.

    Cite this