Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models
Lars Otten, Rina Dechter
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.
Keywords:
Pages: 665-674
PS Link:
PDF Link: /papers/12/p665-otten.pdf
BibTex:
@INPROCEEDINGS{Otten12,
AUTHOR = "Lars Otten and Rina Dechter",
TITLE = "A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models",
BOOKTITLE = "Proceedings of the Twenty-Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-12)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2012",
PAGES = "665--674"
}


hosted by DSL   •   site info   •   help