Semidefinite Relaxations of Ordering Problems

Ordering problems assign weights to each ordering and ask to find an ordering of maximum weight. We consider problems where the cost function is either linear or quadratic. In the first case, there is a given profit if the element u is before v in the ordering. In the second case, the profit depends on … Read more