Kemeny Score Problem (COMSOC)

Definition

Kemeny Score Problem (COMSOC)

Input:

• profile $R=({\succ }_1,\dots ,{\succ }_n)$ over alternatives $C$,
• positive integer $k$

Question: $\exists {\succ }^{\ast }\in \mathcal{L}(C)$ with Kemeny score at most $k$, i.e., $\mathrm{KT}\text{-}\mathrm{dist}({\succ }^{\ast },R)\le k$.

Complexity

The Kemeny score problem is NP-complete.

Algorithms

• $\frac{8}{5}-$constant-factor approximation algorithm
• $\frac{11}{7}$-randomised constant-factor approximation algorithm
• polynomial-time approximation scheme
• exact algorithms
• heuristics
• branch and bound
• experiments