Algorithmic obstructions in the random number partitioning problem
Algorithmic obstructions in the random number partitioning problem
We consider the algorithmic problem of finding a near-optimal solution for the number partitioning problem (NPP). This problem appears in many practical applications, including the design of randomized controlled trials, multiprocessor scheduling, and cryptography. It is also of theoretical significance. The NPP possesses a so-called statistical-to-computational gap: when its input …