Algorithmen für das Zahlenaufteilungsproblem

Das Zahlenaufteilungsproblem (number partitioning problem, NPP) ist eines der zentralen Probleme der theoretischen Informatik. Es ist ausserdem relevant für die statistische Physik, wo es ein Modell für Meanfield-Antiferromagnete darstellt. In diesem Projekt geht es um die Analyse von Algorithmen für das NPP. Insbesondere soll untersucht werden, warum alle gängigen Heuristiken bei diesem Problem versagen, und was genau die Qualität der besten bekannten Algorithmen beschränkt.