Title of article :
Optimal integer partitions
Author/Authors :
Engel، نويسنده , , Konrad and Radzik، نويسنده , , Tadeusz and Schlage-Puchta، نويسنده , , Jan-Christoph، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2014
Abstract :
Let n be a positive integer and let g 1 , … , g n be real numbers. The following integer partition problem (IPP) is studied: find a partition of the integer n = ∑ i = 1 n i ⋅ λ i such that ∑ i = 1 n g i ⋅ λ i is maximal. An extended variant of the IPP is the problem EIPP, where, as a secondary condition, the number ∑ i = 1 n λ i of items has to be minimal. The support of the partition is the index-set of all nonzero items, i.e., { i : λ i > 0 } . It is proved that there is always an optimal solution for the IPP (as well as for the EIPP) whose support contains at most ⌊ log 2 ( n + 1 ) ⌋ elements and that this bound is sharp. An algorithm of time complexity O ( n 2 ) for the determination of such an optimal solution is presented. Finally the following non-polynomial bounds for the maximum number M ( n ) of all optimal solutions for the EIPP are proved: 2.2324 n 1 / 3 ≲ ln M ( n ) ≲ 1 3 6 3 n 1 / 3 ln n as n → ∞ .
Journal title :
European Journal of Combinatorics
Journal title :
European Journal of Combinatorics