A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time
From MaRDI portal
Publication:6589758
DOI10.1007/S10107-023-02044-1MaRDI QIDQ6589758
Tobias Mömke, Víctor Verdugo, Vincent Cohen-Addad
Publication date: 20 August 2024
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- On the Lambert \(w\) function
- 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
- LP Formulations for Polynomial Optimization Problems
- Euclidean distortion and the sparsest cut
- 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 quasipolynomial (2 + ε )-approximation for planar sparsest cut
- An improved parameterized algorithm for treewidth
This page was built for publication: A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6589758)
