# Frameworks to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems

arXiv: https://arxiv.org/abs/2201.08940 · HTML: https://mlsanity.com/paper/2201.08940/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jan 2022.

## Built on by (most cited first, 2 of 2)

- [Ratio Divergence Learning Using Target Energy in Restricted Boltzmann Machines: Beyond Kullback--Leibler Divergence Learning](https://mlsanity.com/paper/2409.07679/) (2024)
- [Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem](https://mlsanity.com/paper/2404.11496/) (2024)

## Abstract (arXiv)

Finding a single best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world problems as objective functions and constraints are only "approximately" formulated for original real-world problems. To solve this issue, finding multiple solutions is a natural direction, and diversity of solutions is an important concept in this context. Unfortunately, finding diverse solutions is much harder than finding a single solution. To cope with difficulty, we investigate the approximability of finding diverse solutions. As a main result, we propose a framework to design approximation algorithms for finding diverse solutions, which yields several outcomes including constant-factor approximation algorithms for finding diverse matchings in graphs and diverse common bases in two matroids and PTASes for finding diverse minimum cuts and interval schedulings.