q-state Potts model for large q

The partition function of the q-state Potts model with random ferromagnetic couplings and large q amounts to minimizing a particular submodular function. Combinatorial optimization algorithms with polynomial running time exist for minimizing a general submodular function. However, in practice the running time of these algorithms grows strongly with the system size. Thus only relatively small instances can be computed. In our case, faster specialized algorithms can be used. We investigate several approaches to further improve these algorithms in order to reach better average running times.