Lasserre integrality gaps for graph spanners and related problems

DOI10.1007/978-3-030-80879-2_7OpenAlexW3183380864MaRDI QIDQ2117692FDOQ2117692

Authors Michael Dinitz, Yasamin Nazari, Ze Yu Zhang 

Publication date 22 March 2022

Full work available at URL https://arxiv.org/abs/1905.07468

Mathematics Subject Classification ID

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

Recommendations

• Integrality gaps for sparsest cut and minimum linear arrangement problems
• Constant factor Lasserre integrality gaps for graph partitioning problems
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• Approximating the norms of graph spanners
• On the Laplacian spread of graphs
• On the Laplacian spread of graphs
• Integrality gaps and approximation algorithms for dispersers and bipartite expanders
• The norms of graph spanners
• Upper bounds on the Laplacian spread of graphs
• Some results on the Laplacian spread of a graph

Cites work

• scientific article; zbMATH DE number 1757962 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• An Optimal Synchronizer for the Hypercube
• Approximating low-stretch spanners
• Approximating spanners and directed Steiner forest: upper and lower bounds
• Approximation algorithms for label cover and the log-density threshold
• Approximation algorithms for spanner problems and directed Steiner forest
• Brief announcement: Characterizing demand graphs for (fixed-parameter) shallow-light Steiner network
• CSP gaps and reductions in the lasserre hierarchy
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Directed spanners via flow-based linear programs
• Fault-tolerant spanners
• Graph spanners
• Improved approximation algorithms for label cover problems
• Label cover instances with large girth and the hardness of approximating basic \(k\)-spanner
• Lowest-degree \(k\)-spanner: approximation and hardness
• Near-optimal algorithms for unique games
• On sparse spanners of weighted graphs
• On the hardness of approximating spanners
• Parallel metric tree embedding based on an algebraic view on Moore-Bellman-Ford
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• The hardness of approximating spanner problems
• Transitive-closure spanners

Cited in

(2)

• Lasserre Integrality Gaps for Graph Spanners and Related Problems
• A note on the integrality gap of the configuration LP for restricted Santa Claus

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 Q2117692)