论文标题
通过分区计算近似子集和比率
Approximating Subset Sum Ratio via Partition Computations
论文作者
论文摘要
我们提出了一个针对子集总和问题问题的新FPTA，鉴于一组整数，它要求两个不相交的子集，以便其总和的比率尽可能接近$ 1 $。我们的计划利用了与密切相关的分区问题的精确算法和近似算法，因此对这些分区问题的任何进展（例如，由于Bringmann和Nakos（Soda 2021]）的最近改进，我们的FPTA都带来了我们的FPTA。根据输入集合$ n $的大小与错误保证金$ \ VAREPSILON $之间的关系，我们改进了Melissinos和Pagourtzis的当前最著名的算法[Cocoon 2018]复杂性$ O（N^4 / \ Varepsilon）$。特别是，根据所使用的分区算法，我们提出的计划中$ n $的指数可能会降至$ 2 $。此外，虽然上述艺术的复杂性状态以$ o（（n + 1 / \ varepsilon）^c）$表示，具有常数$ c = 5 $，但我们的结果表明$ c <5 $。
We present a new FPTAS for the Subset Sum Ratio problem, which, given a set of integers, asks for two disjoint subsets such that the ratio of their sums is as close to $1$ as possible. Our scheme makes use of exact and approximate algorithms for the closely related Partition problem, hence any progress over those -- such as the recent improvement due to Bringmann and Nakos [SODA 2021] -- carries over to our FPTAS. Depending on the relationship between the size of the input set $n$ and the error margin $\varepsilon$, we improve upon the best currently known algorithm of Melissinos and Pagourtzis [COCOON 2018] of complexity $O(n^4 / \varepsilon)$. In particular, the exponent of $n$ in our proposed scheme may decrease down to $2$, depending on the Partition algorithm used. Furthermore, while the aforementioned state of the art complexity, expressed in the form $O((n + 1 / \varepsilon)^c)$, has constant $c = 5$, our results establish that $c < 5$.
