Export Reviews, Discussions, Author Feedback and Meta-Reviews

We thank the reviewers for the detailed comments and feedback. In the following we will address some of the issues that have been raised by the reviewers. Current state-of-the-art is represented by search based algorithms guided by either mini-bucket heuristics (daoopt, AOBB) or soft local consistency (toulbar). These algorithms were compared against each other in the past 2-4 UAI competitions and were shown to be both winning and overall both quite competitive. Since we compare with one of these schemes we believe we compare against state-of-the-art for exact MAP inference. For example, to the best of our knowledge, the type4/largeFam instances shown in Table 4 are solved only by RBFAOO/SPRBFAOO with the mini-bucket heuristics.