An SDP Primal-Dual Approximation Algorithm for Directed Hypergraph Expansion and Sparsest Cut with Product Demands

T-H. Hubert Chan, Bintao Sun

We give approximation algorithms for the edge expansion and sparsest cut with product demands problems on directed hypergraphs, which subsume previous graph models such as undirect…