Papers › Preordering: A hybrid of correlation clustering and partial ordering
Preordering: A hybrid of correlation clustering and partial ordering
Jannik Irmai, Maximilian Moeller, Bjoern Andres
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 linear program formulation, we establish a class of non-canonical facets of the associated preorder polytope. By solving a non-canonical linear program relaxation, we obtain non-trivial upper bounds on the objective value. We provide implementations of the algorithms we define, apply these to published social networks and compare the output and efficiency qualitatively and quantitatively.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections