A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems

Authors

  • Tesshu Hanaka Kyushu University
  • Masashi Kiyomi Seikei University
  • Yasuaki Kobayashi Hokkaido University
  • Yusuke Kobayashi Kyoto University
  • Kazuhiro Kurita Nagoya University
  • Yota Otachi Nagoya University

DOI:

https://doi.org/10.1609/aaai.v37i4.25511

Keywords:

CSO: Other Foundations of Constraint Satisfaction & Optimization, SO: Other Foundations of Search & Optimization

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.

Downloads

Published

2023-06-26

How to Cite

Hanaka, T., Kiyomi, M., Kobayashi, Y., Kobayashi, Y., Kurita, K., & Otachi, Y. (2023). A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4), 3968-3976. https://doi.org/10.1609/aaai.v37i4.25511

Issue

Section

AAAI Technical Track on Constraint Satisfaction and Optimization