Export Reviews, Discussions, Author Feedback and Meta-Reviews

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. Augmentative Message Passing for Traveling Salesman Problem and Graph Partitioning The paper develops messaging passing techniques to approximate two NP-hard problems: TSP and graph partitioning. Using specifics of each problem a graphical model is constructed such that the MAP state gives the solution for the original problem (e.g. using Held-Karp necessary and sufficient conditions for valid tours for the TSP). The resulting model has a very large number of clusters making message passing on the full graph (full set of constraints) infeasible for large problems (even when loops are ignored in the problem and no junction tree is constructed). The paper proposes methods to approximate this by starting with a smaller set of constraints and iteratively adding some. Quality The methods proposed do not come with any guarantee.