  We study the problem of complexity estimation in the context of parallelizing
an advanced Branch and Bound-type algorithm over graphical models. The
algorithm's pruning power makes load balancing, one crucial element of every
distributed system, very challenging. We propose using a statistical regression
model to identify and tackle disproportionally complex parallel subproblems,
the cause of load imbalance, ahead of time. The proposed model is evaluated and
analyzed on various levels and shown to yield robust predictions. We then
demonstrate its effectiveness for load balancing in practice.
