Research map / Learning theory and algorithms / Clustering

Submodular Clustering beyond $1-1/e$

NeurIPS 2026 · Learning theory and algorithms › Clustering · approach: Coresets and dynamic clustering

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 submodular clustering in metric spaces, where k centers are chosen to maximize total service under a decreasing service function, aiming to go beyond the 1-1/e approximation barrier.

Problem

Selecting k centers in a metric space to maximize total service under a decreasing service function (submodular clustering), a problem relevant to influence maximization, data summarization, and representation learning.

Approach

Targets approximation guarantees for submodular clustering that surpass the classical 1-1/e barrier of greedy-style submodular maximization; the abstract as provided does not specify the algorithm.

Closest papers by meaning

• Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy? (ICML 2018 · similarity 0.87)
• Fair Submodular Cover (ICLR 2025 · similarity 0.86)
• Competitively Consistent Clustering (ICML 2025 · similarity 0.86)
• Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.86)
• Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.86)
• Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.86)