Instance space of the number partitioning problem
F F Ferreira, José F. Fontanari · Journal of Physics A Mathematical and General · 2000
Within the replica framework we study analytically the instance space of the number partitioning problem. This classic integer programming problem consists of partitioning a sequence of N positive real numbers { a 1 , a 2 ,..., a N } (the instance) into two sets such that the absolute value of the difference of the sums of a j over the two sets is minimized. We show that, regardless of the distribution of the instance entries, there is an upper bound α c N to the number of perfect random partitions (i.e. partitions for which that difference is zero). In particular, in the case where the two sets have the same cardinality (balanced partitions) we find α c = ½. Moreover, in the case of unbalanced partitions, we show that perfect random partitions exist only if the difference between the cardinalities of the two sets scales like mN 1/2 , where m is of the order of 1.