论文标题
子集比率问题的近似方案
Approximation Schemes for Subset Sum Ratio Problems
论文作者
论文摘要
我们考虑子集总比率问题（$ SSR $），其中给定一组整数的目标是找到两个子集，以便其总和的比率尽可能接近〜1，并引入一个捕获额外有意义要求的变化家族。我们的主要贡献是一个通用框架，该框架为满足某些条件的家庭中的问题提供了完全多项式时间近似方案（FPTA）。我们使用我们的框架来设计两个这样的问题的明确FPTASS，即两套子集的比率和因子 - $ r $子集比率，并且运行时间$ \ MATHCAL {O}（N^4/\ VAREPSILON）$，这与原始$ SSR $ ssr $ $ [15]相吻合。
We consider the Subset Sum Ratio Problem ($SSR$), in which given a set of integers the goal is to find two subsets such that the ratio of their sums is as close to~1 as possible, and introduce a family of variations that capture additional meaningful requirements. Our main contribution is a generic framework that yields fully polynomial time approximation schemes (FPTAS) for problems in this family that meet certain conditions. We use our framework to design explicit FPTASs for two such problems, namely Two-Set Subset-Sum Ratio and Factor-$r$ Subset-Sum Ratio, with running time $\mathcal{O}(n^4/\varepsilon)$, which coincides with the best known running time for the original $SSR$ problem [15].
