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.
Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.
If you think you should have access to this title, please contact your librarian.