摘要 Abstract 

計算多樣解法備受關注而最近工作主要是找最優解。然而最佳解空間有時太小無法有多樣性，所以我們開始研究近似最優解法。將多樣性定為解的距離總和，我們將問題轉化為BCO問題，並證明對BCO的雙近似解可給出雙近似解。

There has been a long-standing interest in computing diverse solutions to optimization problems and recent work has involved finding diverse solutions that are all optimal. However, sometimes, the space of exact solutions may be too small to achieve sufficient diversity. Motivated by this, we initiate the study of obtaining sufficiently-diverse, yet approximately-optimal solutions to optimization problems. With setting the diversity measure as the sum of pairwise distances between solutions, we provide a general reduction to an associated budget-constrained optimization (BCO) problem and then prove that bi-approximations to the BCO can be used to give bi-approximations to our problem.