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 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.
翻译:寻找 emph{ single} 最佳解决方案是组合优化问题中最常见的目标。 但是, 这样的单一解决方案可能不适用于现实世界问题, 因为客观功能和制约只是为原始现实世界问题“ 约” 制定的。 要解决这个问题, 找到 emph{ multiple} 解决方案是一个自然方向, 而解决方案的多样性是这方面的一个重要概念。 不幸的是, 找到不同的解决方案比找到一个单一解决方案要困难得多。 为了应对困难, 我们研究找到不同解决方案的近似算法。 作为主要结果, 我们提出一个框架, 用于设计寻找不同解决方案的近似算法, 从而产生若干结果, 包括用于在图表中找到不同匹配的常数近似算法, 以及在两个配机和 PTASes 中找到不同最小的剪切和间隔时间表的多种共同基础 。