A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Abstract
Finding a \emph{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 \emph{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 the 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.
Cite
Text
Hanaka et al. "A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems." AAAI Conference on Artificial Intelligence, 2023. doi:10.1609/AAAI.V37I4.25511Markdown
[Hanaka et al. "A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems." AAAI Conference on Artificial Intelligence, 2023.](https://mlanthology.org/aaai/2023/hanaka2023aaai-framework/) doi:10.1609/AAAI.V37I4.25511BibTeX
@inproceedings{hanaka2023aaai-framework,
title = {{A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems}},
author = {Hanaka, Tesshu and Kiyomi, Masashi and Kobayashi, Yasuaki and Kobayashi, Yusuke and Kurita, Kazuhiro and Otachi, Yota},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2023},
pages = {3968-3976},
doi = {10.1609/AAAI.V37I4.25511},
url = {https://mlanthology.org/aaai/2023/hanaka2023aaai-framework/}
}