Heiko Bauke, Stephan Mertens, Andreas Engel
Published 2002-08-05, updated 2002-08-21Version 2
The problem of distributing the workload on a parallel computer to minimize the overall runtime is known as Multiprocessor Scheduling Problem. It is NP-hard, but like many other NP-hard problems, the average hardness of random instances displays an ``easy-hard'' phase transition. The transition in Multiprocessor Scheduling can be analyzed using elementary notions from crystallography (Bravais lattices) and statistical mechanics (Potts vectors). The analysis reveals the control parameter of the transition and its critical value including finite size corrections. The transition is identified in the performance of practical scheduling algorithms.
Comments: 6 pages, revtex4
Smearing of the phase transition in Ising systems with planar defects
Finite Size Corrections to Disordered Systems : mean field results and applications to finite dimensional models
Extremal Optimization at the Phase Transition of the 3-Coloring Problem
