The Number Partitioning problem is motivated in particular by the statistical
problem of designing a randomized control study with two groups possessing
roughly ”equal” attributes. It is also a special case of the bin-packing problem, and also has been
widely studied in the statistical physics literature. The Number Partitioning problem will serve as
one of the running
example in this article, illustrating our main ideas, so we introduce it now. Given \(N\)  items with
weights \(X_1,\ldots ,X_N\) , the goal is to split it into
two groups so that the difference of total weights in two groups is the smallest possible.
Namely, the goal is finding a subset \(I\subset 1,\ldots ,N\)  such
that \(|\sum _{i\in I}X_i-\sum _{i\notin I}X_i|\)  is as small as possible.
An NP-hard problem in the worst case [1]},
it is more
tractable in presence of randomness. Suppose, the weights \(X_i\)  are generated
independently according to the standard Gaussian distribution \(\mathcal {N}(0,1)\) .
A rather straightforward application of the same probabilistic method
shows that the optimum value is typically \(\sqrt{N}2^{-N}\)  for large \(N\) .
Namely, the value of \(c^*\) 
in our context is \(\sqrt{N}2^{-N}\) .
An algorithm proposed by Karmarkar and Karp in 1982 [2]}
achieves the value of order \(c_{\rm ALG}=\sqrt{N}e^{-c\log _2^2 N}\) ,
with value \(c\)  predicted (though not proven) to be \(1/(2\log 2)\approx 0.721..~\)  [3]}.
The multiplicative
gap between the two is thus very significant (exponential): \(c_{\rm ALG}/c^*=2^{N-O(\log _2^2 N)}\) .
While multidimensional extensions of this algorithm have been considered
recently [4]},[5]},
no improvement of this result is known to the date,
and no algorithmic hardness result is known either.
