Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion

DOI10.4086/TOC.2016.V012A017zbMATH Open1393.68190arXiv1404.4575OpenAlexW2962780495MaRDI QIDQ2830864FDOQ2830864

Authors: Anand Louis, Yury Makarychev 

Publication date: 1 November 2016

Published in: Theory of Computing (Search for Journal in Brave)

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

Recommendations

• Approximation algorithms for hypergraph small set expansion and small set vertex expansion
• Min-Max Graph Partitioning and Small Set Expansion
• Graph expansion and the unique games conjecture
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms

zbMATH Keywords

approximation algorithmssmall-set expansionhypergraph expansion

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Hypergraphs (05C65)

Cites Work

• Graph expansion and the unique games conjecture
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms

Cited In (6)

• Minimizing the union: tight approximations for small set bipartite vertex expansion
• Graph expansion and the unique games conjecture
• The small set vertex expansion problem
• Finding Cheeger cuts in hypergraphs via heat equation
• Approximation algorithms for hypergraph small set expansion and small set vertex expansion
• The small set vertex expansion problem

Uses Software

• Zoltan

This page was built for publication: Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830864)