Number partitioning

Number partitioning is one of the most basic optimization problems. It is very easy to state: ‘Given the values of N assets, is there a fair partition of them into two sets?’ Nevertheless, it is very difficult to solve: it belongs to the NP-complete category, and the known heuristics are often not very good. It is also a problem with practical applications, for instance in multiprocessor scheduling. This chapter focuses on a particularly difficult case: the partitioning of a list of independent uniformly distributed random numbers. It discusses the phase transition occurring when the range of numbers varies, and shows that low cost configurations — the ones with a small unbalance between the two sets — can be seen as independent energy levels. Hence the model behaves analogously to the Random Energy Model.