Lasserre integrality gaps for graph spanners and related problems
From MaRDI portal
Publication:2117692
DOI10.1007/978-3-030-80879-2_7OpenAlexW3183380864MaRDI QIDQ2117692
Michael Dinitz, Yasamin Nazari, Ze Yu Zhang
Publication date: 22 March 2022
Full work available at URL: https://arxiv.org/abs/1905.07468
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for label cover problems
- On sparse spanners of weighted graphs
- Approximation algorithms for spanner problems and directed Steiner forest
- The hardness of approximating spanner problems
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner
- Near-optimal algorithms for unique games
- Fault-tolerant spanners
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Graph spanners
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Approximating Low-Stretch Spanners
- Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
- Approximation Algorithms for Label Cover and The Log-Density Threshold
- Parallel Metric Tree Embedding Based on an Algebraic View on Moore-Bellman-Ford
- An Optimal Synchronizer for the Hypercube
- Transitive-Closure Spanners
- CSP gaps and reductions in the lasserre hierarchy
- Directed spanners via flow-based linear programs
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- On the hardness of approximating spanners
This page was built for publication: Lasserre integrality gaps for graph spanners and related problems
