Approximation Algorithm for Sparsest k-Partitioning

DOI10.1137/1.9781611973402.92zbMath1422.68306arXiv1306.4384OpenAlexW2490668581MaRDI QIDQ5384054

Anand Louis, Konstantin Makarychev

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (6)

Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Minimum nonuniform graph partitioning with unrelated weights ⋮ Multi-way sparsest cut problem on trees with a control on the number of parts and outliers ⋮ Approximation Algorithms for CSPs ⋮ Generalizing the hypergraph Laplacian via a diffusion process with mediators ⋮ Diffusion operator and spectral analysis for directed hypergraph Laplacian

This page was built for publication: Approximation Algorithm for Sparsest k-Partitioning