A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi
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.
BibTeX
@article{Hanaka_Kiyomi_Kobayashi_Kobayashi_Kurita_Otachi_2023, title={A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/25511}, DOI={10.1609/aaai.v37i4.25511}, abstractNote={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.}, number={4}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Hanaka, Tesshu and Kiyomi, Masashi and Kobayashi, Yasuaki and Kobayashi, Yusuke and Kurita, Kazuhiro and Otachi, Yota}, year={2023}, month={Jun.}, pages={3968-3976} }