论文标题
设计近似算法的框架，用于在组合问题中找到多种解决方案
A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
论文作者
论文摘要
找到一个\ emph {单}最佳解决方案是组合优化问题中最常见的目标。但是，这样的单个解决方案可能不适用于现实世界中的问题，因为目标函数和约束仅是针对原始现实世界中的问题“近似”的。为了解决这个问题，找到\ emph {多}解决方案是一个自然的方向，在这种情况下，解决方案的多样性是一个重要的概念。不幸的是，找到多样化的解决方案要比找到单个解决方案要困难得多。为了应付困难，我们研究了寻找多种解决方案的近似性。作为主要结果，我们提出了一个框架来设计用于查找各种解决方案的近似算法，该算法产生了几个结果，包括恒定因素近似算法，用于在图形中找到各种匹配和在两个矩形和PTases中的多样共同基础，以找到各种最小的切割和间隔时间表。
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.
