Preordering: A hybrid of

Preordering: A hybrid of
Preordering: A hybrid of correlation clustering and partial ordering

We discuss the preordering problem, a joint relaxation of the correlation clustering problem and the partial ordering problem. We show that preordering remains NP-hard even for values in ${-1,0,1}$. We introduce a linear-time $4$-approximation algorithm and a local search technique. For an integer l…