Mean Isoperimetry with Control on Outliers: Exact and Approximation Algorithms

Morteza Alimi, Amir Daneshgar, Mohammad-Hadi Foroughmand-Araabi

Given a weighted graph $G=(V,E)$ with weight functions $c:E\to {\mathbb{R}}_{+}$ and $\pi :V\to {\mathbb{R}}_{+}$, and a subset $U\subseteq V$, the normalized cut value for $U$ is defined as…