English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study two mixed robust/average-case submodular partitioning problems thatwe collectively call Submodular Partitioning. These problems generalize bothpurely robust instances of the problem (namely max-min submodular fairallocation (SFA) and min-max submodular load balancing (SLB) and alsogeneralize average-case instances (that is the submodular welfare problem (SWP)and submodular multiway partition (SMP). While the robust versions have beenstudied in the theory community, existing work has focused on tightapproximation guarantees, and the resultant algorithms are not, in general,scalable to very large real-world applications. This is in contrast to theaverage case, where most of the algorithms are scalable. In the present paper,we bridge this gap, by proposing several new algorithms (including those basedon greedy, majorization-minimization, minorization-maximization, and relaxationalgorithms) that not only scale to large sizes but that also achievetheoretical approximation guarantees close to the state-of-the-art, and in somecases achieve new tight bounds. We also provide new scalable algorithms thatapply to additive combinations of the robust and average-case extremeobjectives. We show that these problems have many applications in machinelearning (ML). This includes: 1) data partitioning and load balancing fordistributed machine algorithms on parallel machines; 2) data clustering; and 3)multi-label image segmentation with (only) Boolean submodular functions viapixel partitioning. We empirically demonstrate the efficacy of our algorithmson real-world problems involving data partitioning for distributed optimizationof standard machine learning objectives (including both convex and deep neuralnetwork objectives), and also on purely unsupervised (i.e., no supervised orsemi-supervised learning, and no interactive segmentation) image segmentation.

Mixed Robust/Average Submodular Partitioning: Fast Algorithms,  Guarantees, and Applications to Parallel Machine Learning and Multi-Label  Image Segmentation