A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
复制标题
DOI：
10.1609/aaai.v37i4.25511
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
T. Hanaka;Masashi Kiyomi;Yasuaki Kobayashi;Yusuke Kobayashi;Kazuhiro Kurita;Y. Otachi
中科院分区：
文献类型：
--
作者：
T. Hanaka;Masashi Kiyomi;Yasuaki Kobayashi;Yusuke Kobayashi;Kazuhiro Kurita;Y. Otachi
在组合优化问题中，寻找\emph{单个}最优解是最常见的目标。然而，这样一个单一的解决方案可能并不适用于现实世界的问题，因为目标函数和约束只是“近似”地为原始的现实世界问题制定的。要解决这个问题，寻找\emph{多种}解决方案是一个自然的方向，而解决方案的多样性是这个背景下的一个重要概念。不幸的是，找到多种解决方案比找到单一解决方案要困难得多。为了解决这个困难，我们研究了寻找不同解的近似性。作为主要结果，我们提出了一个框架来设计寻找不同解的近似算法，它产生了几个结果，包括用于寻找图中不同匹配和两个拟阵中的不同公共基的常因子近似算法和用于寻找不同最小切割和区间调度的pase。
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.