This paper is about a complexity estimation of using distributed algorithm for branch-and-bound over graphical models. The paper proposes a distributed/parallel Branch-and-Bound algorithm and evaluates its efficiency for load balancing. The ability to search multiple sub problem in parallel for the same problem would speed up the search significantly. However, balancing the parallel search load is important for efficiency. This paper does a complete case study of learning how to parallelize And-Or graph using Branch and Bound search. They use a set of features collected from the graph (static) or from the search problem (dynamic) for the problem and evaluate each of the three learning cases: per problem instances, per problem class, and across problem class using linear and non-linear regression methods.T hey extensively evaluate all the possible combinations and show the pros and cons of using each type of learning.
Pros: The paper is well written, and covers all the possibilities for learning and has a good discussion that educates the reader. The evaluations are extensive and conclusive. The literature review is complete.
Cons: From a practicality point of view, the bottle neck problem is not discussed, when would parallelizing AOGBB be bad? Also the motivation for choosing the features that they used, are they standard set of features? (the good point is that they showed that some of the features were more important than other based on their experiments).