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. The authors derive a new convex relaxation for the noisy seriation problem (a combinatorial ordering problem, where variables must be ordered on a line such that their pairwise similarities decrease with their distance on this line). Specifically, they use the construction in Goemans [1] based on sorting networks, in order to optimize over the convex set of permutation vectors (ie. the permutahedron) instead of the convex hull of permutation matrices (ie. the Birkhoff polytope). The new representation reduces the number of constraints from Theta(n^2) to Theta(nlog^2n) and turns out to be in practice significantly faster to solve some instances of the seriation problem. I think this paper provides a very appealing convex relaxation to the seriation problem, since it enables to solve much larger instances (up to several thousands with a standard interior point solver, against to a few hundreds with previous relaxation in [2]).