A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
From MaRDI portal
Publication:2164684
DOI10.1007/978-3-031-06901-7_9zbMath1497.90211arXiv2111.06163OpenAlexW4285146977MaRDI QIDQ2164684
Vincent Cohen-Addad, Tobias Mömke, Víctor Verdugo
Publication date: 16 August 2022
Full work available at URL: https://arxiv.org/abs/2111.06163
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Cites Work
- Unnamed Item
- Cuts, trees and \(\ell_1\)-embeddings of graphs
- Sparsest cuts and bottlenecks in graphs
- Coarse differentiation and multi-flows in planar graphs
- Multicommodity flows in planar graphs
- An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
- Flow-cut gaps for integer and fractional multiflows
- Breaking symmetries to rescue sum of squares in the case of makespan scheduling
- Tree-width and the Sherali-Adams operator
- Pathwidth, trees, and random embeddings
- On the hardness of approximating Multicut and Sparsest-Cut
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Approximating Sparsest Cut in Graphs of Bounded Treewidth
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- LP Formulations for Polynomial Optimization Problems
- Quasi-PTAS for scheduling with precedences using LP hierarchies
- Euclidean distortion and the sparsest cut
- Sparsest cut on bounded treewidth graphs
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
- Expander flows, geometric embeddings and graph partitioning
- A tight approximation algorithm for the cluster vertex deletion problem
- A quasipolynomial (2 + ε )-approximation for planar sparsest cut
This page was built for publication: A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
