Approximating submodular $k$-partition via principal partition sequence

Karthekeyan Chandrasekaran, Weihang Wang

In submodular $k$-partition, the input is a non-negative submodular function $f$ defined over a finite ground set $V$ (given by an evaluation oracle) along with a positive integer…