Phase diagram for the constrained integer partitioning problem
Phase diagram for the constrained integer partitioning problem
复制标题
约束整数划分问题的相图
DOI：
10.1002/rsa.20001
复制
发表时间：
2003
影响因子：
1
通讯作者：
B. Pittel
中科院分区：
文献类型：
--
作者：
C. Borgs;J. Chayes;S. Mertens;B. Pittel
我们考虑将n个整数分成给定基数的两个子集的问题，使得差，即它们的和的差的绝对值，被最小化。这些数字都是身份证。从集合{1，…}中均匀选择的随机变量、M}。我们研究了最优划分的典型行为如何依赖于n，M和偏差S，即划分中两个子集的基数之差。特别地，我们严格地将这一典型行为建立为两个参数κ：=n−1log2M和b：=|S|/n的函数，通过证明κb平面中存在三个不同的“阶段”，其特征是差异的值和最优解的数量：具有指数级多个差异为0或1的最优解的“完美阶段”；具有最小差异阶为Me−Θ(N)的“硬阶段”；以及通过将(S+n)/2个最小整数放入一个子集而获得的具有唯一最优划分的“排序阶段”。我们的相图覆盖了κb平面上的所有区域，除了相对较小的区域。我们还证明了这三个阶段可以交替地用相关线性规划问题的基解的数目和这些基解的分数来刻画，这些基解的±1-值分量形成具有相应权重的子问题的最优整数划分。特别地，我们证明了这个分数在分类相中是1，并且在完美相和硬相中都是指数小的，并且在硬相中严格地指数小于完美相。讨论了尚待解决的问题，并给出了数值实验。©2004威利期刊公司随机结构。高，2004年
We consider the problem of partitioning n integers into two subsets of given cardinalities such that the discrepancy, the absolute value of the difference of their sums, is minimized. The integers are i.i.d. random variables chosen uniformly from the set {1,…,M}. We study how the typical behavior of the optimal partition depends on n, M, and the bias s, the difference between the cardinalities of the two subsets in the partition. In particular, we rigorously establish this typical behavior as a function of the two parameters κ :=n−1log2M and b := |s|/n by proving the existence of three distinct “phases” in the κb‐plane, characterized by the value of the discrepancy and the number of optimal solutions: a “perfect phase” with exponentially many optimal solutions with discrepancy 0 or 1; a “hard phase” with minimal discrepancy of order Me−Θ(n); and a “sorted phase” with an unique optimal partition with discrepancy of order Mn, obtained by putting the (s + n)/2 smallest integers in one subset. Our phase diagram covers all but a relatively small region in the κb‐plane. We also show that the three phases can be alternatively characterized by the number of basis solutions of the associated linear programming problem, and by the fraction of these basis solutions whose ±1‐valued components form optimal integer partitions of the subproblem with the corresponding weights. We show in particular that this fraction is one in the sorted phase, and exponentially small in both the perfect and hard phases, and strictly exponentially smaller in the hard phase than in the perfect phase. Open problems are discussed, and numerical experiments are presented. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004