Feasibility criteria for high-multiplicity partitioning problems
Feasibility criteria for high-multiplicity partitioning problems
复制标题
高重数划分问题的可行性标准
DOI：
10.1016/j.jpaa.2021.106937
复制
发表时间：
2022
影响因子：
0.8
通讯作者：
Raicu, Claudiu
中科院分区：
文献类型：
--
作者：
Raicu, Claudiu
对于固定的权重w 1，n，w n，且d> 0，我们让B表示d n个球的集合，其中d个球的权重为w i，对于每个i= 1，n，n。我们考虑的问题，分配球的容量为C1，C2，Cn的n个箱子，在这样的方式，每个箱子被分配d球，而不超过其容量。当d ≥ 0时，我们给出了这个问题可行性的充分判据，这些判据与自然的必要条件集在显式常数上一致。此外，我们表明，我们的常数是最佳的权重时，我是不同的。我们在这里提出的可行性准则可用于其他地方（交换代数中）来研究对称单项理想的Castelnuovo-Mumford正则性的渐进行为。
For fixed weights w 1,⋯, w n, and for d> 0, we let B denote a collection of d⋅ n balls, with d balls of weight w i for each i= 1,⋯, n. We consider the problem of assigning the balls to n bins with capacities C 1,⋯, C n, in such a way that each bin is assigned d balls, without exceeding its capacity. When d≫ 0, we give sufficient criteria for the feasibility of this problem, which coincide up to explicit constants with the natural set of necessary conditions. Furthermore, we show that our constants are optimal when the weights w i are distinct. The feasibility criteria that we present here are used elsewhere (in commutative algebra) to study the asymptotic behavior of the Castelnuovo–Mumford regularity of symmetric monomial ideals.
影响因子：
2.7
作者：
C. Filippi;A. Agnetis
通讯作者：
A. Agnetis
具有少量作业长度的多处理器调度的多项式算法
DOI：
--
发表时间：
1997
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
S. McCormick;Scott R. Smallwood;F. Spieksma
通讯作者：
F. Spieksma