Lasserre integrality gaps for graph spanners and related problems
From MaRDI portal
Publication:2117692
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
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
- scientific article; zbMATH DE number 7650078
- On the Laplacian spread of graphs
- On the Laplacian spread of graphs
- Integrality gaps and approximation algorithms for dispersers and bipartite expanders
- scientific article; zbMATH DE number 7561533
- Upper bounds on the Laplacian spread of graphs
- Some results on the Laplacian spread of a graph
Cites Work
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- An Optimal Synchronizer for the Hypercube
- Transitive-closure spanners
- On sparse spanners of weighted graphs
- Graph spanners
- Fault-tolerant spanners
- Title not available (Why is that?)
- Title not available (Why is that?)
- The hardness of approximating spanner problems
- Improved approximation algorithms for label cover problems
- Near-optimal algorithms for unique games
- On the hardness of approximating spanners
- CSP gaps and reductions in the lasserre hierarchy
- Directed spanners via flow-based linear programs
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Approximation algorithms for spanner problems and directed Steiner forest
- Lowest-degree \(k\)-spanner: approximation and hardness
- Approximating low-stretch spanners
- Approximating spanners and directed Steiner forest: upper and lower bounds
- Parallel metric tree embedding based on an algebraic view on Moore-Bellman-Ford
- Label cover instances with large girth and the hardness of approximating basic \(k\)-spanner
- Approximation algorithms for label cover and the log-density threshold
- Brief announcement: Characterizing demand graphs for (fixed-parameter) shallow-light Steiner network
Cited In (2)
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)
