# GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility

Source: [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](<https://www.sota2.com/research/paper/68fa7c3c1e209131cea8d15a>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-28T10:37:22.551Z

Authors: Matthew Fahrbach, Srikumar Ramalingam, Morteza Zadimoghaddam, Sara Ahmadian, Gui Citovsky, Giulia DeSalvo

Published: 2024-05-29T04:39:24.000Z

## Abstract

This work studies a novel subset selection problem called max-min diversification with monotone submodular utility ($\\textsf{MDMS}$), which has a wide range of applications in machine learning, e.g., data sampling and feature selection. Given a set of points in a metric space, the goal of $\\textsf{MDMS}$ is to maximize $f(S) = g(S) + \\lambda \\cdot \\texttt{div}(S)$ subject to a cardinality constraint $\|S\| \\le k$, where $g(S)$ is a monotone submodular function and $\\texttt{div}(S) = \\min\_{u,v \\in S : u \\ne v} \\text{dist}(u,v)$ is the max-min diversity objective. We propose the $\\texttt{GIST}$ algorithm, which gives a $\\frac{1}{2}$-approximation guarantee for $\\textsf{MDMS}$ by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove that it is NP-hard to approximate within a factor of $0.5584$. Finally, we show in our empirical study that $\\texttt{GIST}$ outperforms state-of-the-art benchmarks for a single-shot data sampling task on ImageNet.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2405.18754>)

[PDF](<https://arxiv.org/pdf/2405.18754.pdf>)
