[EM] NP hardness cites for Kemeny

[Warren Smith]

Rank Aggregation Revisited
Cynthia Dwork, Ravi Kumar, Moni Naor, D. Sivakumar
http://www.eecs.harvard.edu/~michaelm/CS222/rank2.pdf

J. J. Bartholdi, C. A. Tovey, and M. A. Trick: Voting schemes for
which it can be difficult to tell who won the
election, Social Choice and Welfare, 6(2):157–165, 1989.

A Computational Study of the Kemeny Rule for Preference Aggregation
Andrew Davenport and Jayant Kalagnanam
http://www.aaai.org/Papers/AAAI/2004/AAAI04-110.pdf

Cohen, W.; Schapire, R.; and Singer, Y. 1999. Learning to order
things. Journal of Artificial Intelligence Research 10:213-270.
http://www.jair.org/media/587/live-587-1788-jair.ps

etc
and it should be noted that it is NP-complete to find an ordering better than X,
and also NP-hard merely to find the Kemeny winner...

-- 
Warren D. Smith
http://RangeVoting.org  <-- add your endorsement (by clicking
"endorse" as 1st step)