Constrained Integer Partitions - Borgs, Christian; Chayes, Jennifer; Mertens, S.; Pittel, B. (Proceedings of the 6th Latin American Symposium on Theoretical Information (LATIN) 59-68, Lecture Notes in Computer Science 2976, 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 f1; ... ;Mg. 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¡1 log2M and b := jsj=n by proving the existence of three distinct " in the ·b-plane, characterized by the value of the discrepancy and the number of optimal solutions: a phase" with exponentially many optimal solutions with discrepancy 0 or 1; a phase" with minimal discrepancy of order Me¡£(n); and a phase" with an unique optimal partition of order Mn, obtained by putting the (s + n)=2 smallest integers in one subset.