论文标题
通过分裂和间隔目标进行不对称的数字分区
Asymmetric Number Partitioning with Splitting and Interval Targets
论文作者
论文摘要
N向数分配问题是组合优化的基本挑战，对公平分配和机器调度等应用具有重大影响。尽管存在这些问题是NP-固定的，但仍有许多近似技术。我们考虑了三种密切相关的近似值，以及各种目标，例如决策，最小值，最大值，甚至是一个广义的目标，其中箱不再被视为相同的，而是不对称（用于将公平的分裂求解不对称或统一的机器调度问题）。 前两个变体优化了分区，以便：在第一个变体中，一些固定的项目可以在两个或更多箱之间分配，而在第二个变体中，我们最多允许固定的数字t分组。第三个变体是一个决策问题：最大的bin和必须在预先指定的间隔内，由固定有理数u乘以最大项目大小的固定有理数u。 当垃圾箱N的数量无限时，我们表明每个变体都是强烈的NP组件。固定垃圾箱N的数量时，运行时间取决于固定参数s，t，u。对于每个变体，我们都会完整地了解其运行时间。 对于n = 2，运行时间很容易识别。我们的主要结果考虑任何固定的n> = 3。使用第一个和第三个变体之间的双向多项式时间缩短，我们表明，如果S> = n-2，则可以在多项式时间内求解n-way数字分区，否则它将是NP完整的。同样，如果t> = n-1，则可以在多项式时间内求解使用T分裂的N向数分区，否则它将是NP完整的。最后，我们表明，如果u> =（n-2）/n，则可以在多项式时间内求解第三个变体，否则它将是NP完整的。我们针对优化问题的积极结果考虑了不对称的Min-Max和不对称的Max-Min版本。
The n-way number partitioning problem, a fundamental challenge in combinatorial optimization, has significant implications for applications such as fair division and machine scheduling. Despite these problems being NP-hard, many approximation techniques exist. We consider three closely related kinds of approximations, and various objectives such as decision, min-max, max-min, and even a generalized objective, in which the bins are not considered identical anymore, but rather asymmetric (used to solve fair division to asymmetric agents or uniform machine scheduling problems). The first two variants optimize the partition such that: in the first variant some fixed number s of items can be split between two or more bins and in the second variant we allow at most a fixed number t of splittings. The third variant is a decision problem: the largest bin sum must be within a pre-specified interval, parameterized by a fixed rational number u times the largest item size. When the number of bins n is unbounded, we show that every variant is strongly NP-complete. When the number of bins n is fixed, the running time depends on the fixed parameters s,t,u. For each variant, we give a complete picture of its running time. For n=2, the running time is easy to identify. Our main results consider any fixed n>=3. Using a two-way polynomial-time reduction between the first and the third variant, we show that n-way number-partitioning with s split items can be solved in polynomial time if s>=n-2, and it is NP-complete otherwise. Also, n-way number-partitioning with t splittings can be solved in polynomial time if t>=n-1, and it is NP-complete otherwise. Finally, we show that the third variant can be solved in polynomial time if u>=(n-2)/n, and it is NP-complete otherwise. Our positive results for the optimization problems consider both asymmetric min-max and asymmetric max-min versions.
