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 algorithmshypergraph expansionsmall-set expansion

Mathematics Subject Classification ID

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

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

(8)

• Finding Cheeger cuts in hypergraphs via heat equation
• The small set vertex expansion problem
• The small set vertex expansion problem
• Graph expansion and the unique games conjecture
• Approximation algorithms for hypergraph small set expansion and small set vertex expansion
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• Sparse cuts in hypergraphs from random walks on simplicial complexes
• Submodular hypergraph partitioning: metric relaxations and fast algorithms via an improved cut-matching game

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)