Definition Kemeny Score Problem (COMSOC) Input: profile over alternatives , positive integer Question: with Kemeny score at most , i.e., . Complexity The Kemeny score problem is NP-complete. Algorithms constant-factor approximation algorithm -randomised constant-factor approximation algorithm polynomial-time approximation scheme exact algorithms heuristics branch and bound experiments