Research map / Learning theory and algorithms / Combinatorial and search optimization
Linear Relaxations for Finding Diverse Elements in Metric Spaces
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Adding greedy augmentation after LP rounding to reach exactly k points (augmented LP) versus plain LP rounding (ablation) | LP-based sum-min diversity algorithm · Madelon, USPS (approximation vs upper bound) | fraction of upper bound achieved | Helped |
| LP-based algorithm vs greedy and local search for sum-min objective | sum-min diversity maximization · COIL100, Madelon, USPS | sum-min objective value | No clear effect |
| Optimizing sum-min instead of sum-sum objective for subset selection | diverse subset selection · COIL100, CDK2 cluster coverage | number of distinct clusters covered and non-uniformity | Helped |
| Adding a coverage/relevance secondary objective to the LP | sum-min diversity LP · theoretical guarantee with coverage | approximation for sum-min and coverage | No clear effect |
| Greedy and local search heuristics for sum-min (instead of LP) | sum-min diversity · worst-case | approximation ratio: O(1/sqrt(k)) | Hurt |
Closest papers by meaning
- Individually Fair Diversity Maximization (NeurIPS 2025 · similarity 0.90)
- Measures of diversity and space-filling designs for categorical data (ICML 2024 · similarity 0.87)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.85)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.85)
- Approximation Scheme for Weighted Metric Clustering via Sherali-Adams (AAAI 2024 · similarity 0.85)
- GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.