On Sparsest Cut and Conductance in Directed Polymatroidal Networks
Preprint
Abstract
We consider algorithms and spectral bounds for sparsest cut and conductance in directed polymatrodal networks. This is motivated by recent work on submodular hypergraphs \cite{Yoshida19,LiM18,ChenOT23,Veldt23} and previous work on multicommodity flows and cuts in polymatrodial networks \cite{ChekuriKRV15}. We obtain three results. First, we obtain an $O(\sqrt{\log n})$-approximation for sparsest cut and point out how this generalizes the result in \cite{ChenOT23}. Second, we consider the symmetric version of conductance and obtain an $O(\sqrt{OPT \log r})$ approximation where $r$ is the maximum degree and we point out how this generalizes previous work on vertex expansion in graphs. Third, we prove a non-constructive Cheeger like inequality that generalizes previous work on hypergraphs. We provide a unified treatment via line-embeddings which were shown to be effective for submodular cuts in \cite{ChekuriKRV15}.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Capacity of Multiple Unicast in Wireless Networks: A Polymatroidal ApproachIEEE Transactions on Information Theory, 2014
- Submodularity beyond submodular energies: Coupling edges in graph cuts2011
- On Average Distortion of Embedding Metrics into the LineDiscrete & Computational Geometry, 2008
- Improved Approximation Algorithms for Minimum Weight Vertex SeparatorsSIAM Journal on Computing, 2008
- Cuts, Trees and ℓ1-Embeddings of Graphs*Combinatorica, 2004
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995
- Eigenvalues and expandersCombinatorica, 1986
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985
- A Min-Max Relation for Submodular Functions on Graphs1977
- Cutsets and partitions of hypergraphsNetworks, 1973