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

DOI10.4086/TOC.2016.V012A017MaRDI QIDQ2830864zbMATH OpenOpenAlexFDO

Authors Anand Louis, Yury Makarychev

Publication date 1 November 2016

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

approximation algorithmssmall-set expansionhypergraph expansion

Mathematics Subject Classification ID

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

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

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

Describes a project that uses

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)