Research map / Learning theory and algorithms / Combinatorial and search optimization
A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
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 |
|---|---|---|---|
| Use top-k weighted-solution enumeration with local search to construct diverse solutions | MAX-SUM DIVERSE SOLUTIONS · Combinatorial problems with a polynomial-time top-k enumeration algorithm | approximation factor: max(1−2/k, 1/2) | Helped |
| Apply the framework to matchings | DIVERSE MATCHINGS · Graphs | approximation factor: max(1 − 2/k, 1/2) | Helped |
| Apply the framework to common bases of two matroids | DIVERSE MATROID COMMON BASES · Two matroids | approximation factor: max(1 − 2/k, 1/2) | Helped |
| Enumerate minimum cuts and apply the framework | DIVERSE MINIMUM CUTS · Graphs | approximation guarantee | Helped |
| Use dynamic programming for fixed k and apply the framework | DIVERSE INTERVAL SCHEDULINGS · Interval schedulings | approximation guarantee | Helped |
Closest papers by meaning
- Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover (AAAI 2024 · similarity 0.88)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.87)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.85)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.85)
- Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation (ICML 2025 · similarity 0.85)
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.85)
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.