A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models
This work addresses load balancing issues in distributed systems for graphical model optimization, but it is incremental as it applies a known statistical method to a specific bottleneck.
The paper tackled the challenge of load balancing in parallel Branch-and-Bound algorithms over graphical models by proposing a statistical regression model to predict and address complex subproblems ahead of time, demonstrating its effectiveness in practice.
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.