Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion

DOI10.1137/1.9781611974782.56zbMath1411.68184arXiv1611.07866OpenAlexW2950509221MaRDI QIDQ4575795

Yury Makarychev, Eden Chlamtáč, Michael Dinitz

Publication date: 16 July 2018

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (10)

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ The maximum exposure problem ⋮ The Densest $k$-Subhypergraph Problem ⋮ Unnamed Item ⋮ The Small Set Vertex expansion problem ⋮ The Maximum Exposure Problem. ⋮ Unnamed Item ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ Approximation algorithm for minimum partial multi-cover under a geometric setting

This page was built for publication: Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion