Combining all these pairwise preferences to find the best global reordering is NP-hard.
we present a non-trivial O(n 3) algorithm, based on chart parsing, that at least finds the best reordering within a certain exponentially large neighborhood.