Research map / Learning theory and algorithms / Submodular and game algorithms

Diversity Maximization: Algorithms for Distant $k$-Subsets

NeurIPS 2026 · Learning theory and algorithms › Submodular and game algorithms · approach: Streaming submodular algorithms

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies the Distant k-Subsets Problem (DKSP), finding two disjoint k-subsets of a metric space that maximize a diversity objective between them.

Problem

Diversity maximization in metric spaces: selecting two disjoint size-k subsets of a metric space that are maximally distant from each other (the Distant k-Subsets Problem), relevant to fairness-aware ML, clustering, and data summarization.

Approach

Theoretical algorithms for DKSP on general metric spaces; the abstract is truncated so the specific approximation technique and objective details are not stated.

Closest papers by meaning

• An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.87)
• GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility (NeurIPS 2025 · similarity 0.86)
• Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma (NeurIPS 2024 · similarity 0.86)
• Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures (ICML 2025 · similarity 0.86)
• Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.86)
• Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.86)