Export Reviews, Discussions, Author Feedback and Meta-Reviews

The paper proposes new algorithms to address a set of problems falling under the umbrella term of'submodular partitioning' - including two distinct clustering problems, namely clustering to maximize homogeneity, or clustering so as to maximize the representation power of every cluster (e.g. The authors consider the case where common costs are applied to each cluster (homogeneous case), or when distinct costs are applied to every cluster (hetergoeneous). Adding to this split, the authors also treat a mix of a robust and an average loss (e.g. a linear combination of the the max distortion with the average distortion when clustering). Starting from the observation that the algorithms working for the robust variants are not scalable, the authors proceed to propose (i) greedy algorithms for the robust homogeneous/heterogeneous algorithms with approximation guarantees, and (ii) a simple method for blending the solutions to the robust and the average cost optimizations. They then proceed to practical examples, demonstrating improvements over baseline algorithms for clustering.