A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models

Lars Otten, Rina Dechter
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:664-673, 2012.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-otten12a, title = {A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models}, author = {Otten, Lars and Dechter, Rina}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {664--673}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/otten12a/otten12a.pdf}, url = {https://proceedings.mlr.press/r10/otten12a.html}, abstract = {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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models %A Lars Otten %A Rina Dechter %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-otten12a %I PMLR %P 664--673 %U https://proceedings.mlr.press/r10/otten12a.html %V R10 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Otten, L. & Dechter, R.. (2012). A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:664-673 Available from https://proceedings.mlr.press/r10/otten12a.html. Reissued by PMLR on 04 October 2026.

Related Material