کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653622 | 1632783 | 2014 | 12 صفحه PDF | دانلود رایگان |
Let nn be a positive integer and let g1,…,gng1,…,gn be real numbers. The following integer partition problem (IPP) is studied: find a partition of the integer n=∑i=1ni⋅λi such that ∑i=1ngi⋅λi is maximal. An extended variant of the IPP is the problem EIPP, where, as a secondary condition, the number ∑i=1nλ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}{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 ⌊log2(n+1)⌋⌊log2(n+1)⌋ elements and that this bound is sharp. An algorithm of time complexity O(n2)O(n2) for the determination of such an optimal solution is presented. Finally the following non-polynomial bounds for the maximum number M(n)M(n) of all optimal solutions for the EIPP are proved: 2.2324n1/3≲lnM(n)≲1363n1/3lnn as n→∞.
Journal: European Journal of Combinatorics - Volume 36, February 2014, Pages 425–436