The Kemeny Rank Aggregation (KRA) problem is a well-studied problem in the
field of Social Choice with a variety of applications in many different areas
like databases and search engines. Intuitively, given a set of votes over a set
of candidates, the problem asks to find an aggregated ranking of candidates
that minimizes the overall dissatisfaction concerning the votes. Recently, a
diverse version of KRA was considered which asks for a sufficiently diverse set
of sufficiently good solutions. The framework of diversity of solutions is a
young and thriving topic in the field of artificial intelligence. The main idea
is to provide the user with not just one, but with a set of different
solutions, enabling her to pick a sufficiently good solution that satisfies
additional subjective criteria that are hard or impossible to model.
In this work, we use a quantum annealer to solve the KRA problem and to
compute a representative set of solutions. Quantum annealing is a meta search
heuristic that does not only show promising runtime behavior on currently
existing prototypes but also samples the solutions space in an inherently
different way, making use of quantum effects. We describe how KRA instances can
be solved by a quantum annealer and provide an implementation as well as
experimental evaluations. As existing quantum annealers are still restricted in
their number of qubits, we further implement two different data reduction rules
that can split an instance into a set of smaller instances. In our evaluation,
we compare classical heuristics that allow to sample multiple solutions such as
simulated annealing and local search with quantum annealing performed on a
physical quantum annealer. We compare runtime, quality of solution, and
diversity of solutions, with and without applying preceding data reduction
rules.

本文描述并实现了如何使用量子退火器解决 Kemeny Rank Aggregation 问题，并使用 2 种数据缩减规则与模拟退火和局部搜索等经典算法进行对比研究量子退火器的运行时间、解决方案的质量和多样性。

基于量子退火的多样化 Kemeny 排名聚合启发式算法

Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing

In its most traditional setting, the main concern of optimization theory is
the search for optimal solutions for instances of a given computational
problem. A recent trend of research in artificial intelligence, called solution
diversity, has focused on the development of notions of optimality that may be
more appropriate in settings where subjectivity is essential. The idea is that
instead of aiming at the development of algorithms that output a single optimal
solution, the goal is to investigate algorithms that output a small set of
sufficiently good solutions that are sufficiently diverse from one another. In
this way, the user has the opportunity to choose the solution that is most
appropriate to the context at hand. It also displays the richness of the
solution space.
When combined with techniques from parameterized complexity theory, the
paradigm of diversity of solutions offers a powerful algorithmic framework to
address problems of practical relevance. In this work, we investigate the
impact of this combination in the field of Kemeny Rank Aggregation, a
well-studied class of problems lying in the intersection of order theory and
social choice theory and also in the field of order theory itself. In
particular, we show that the Kemeny Rank Aggregation problem is fixed-parameter
tractable with respect to natural parameters providing natural formalizations
of the notions of diversity and of the notion of a sufficiently good solution.
Our main results work both when considering the traditional setting of
aggregation over linearly ordered votes, and in the more general setting where
votes are partially ordered.

研究表明，通过将方案多样性与参数化复杂性理论相结合，可以使用基于算法的框架解决实际相关问题，例如 Kemeny Rank 聚合问题。

Kemeny 排名聚合的多样性：参数化方法

Diversity in Kemeny Rank Aggregation: A Parameterized Approach

We study fixed parameter algorithms for three problems: Kemeny rank
aggregation, feedback arc set tournament, and betweenness tournament. For
Kemeny rank aggregation we give an algorithm with runtime O*(2^O(sqrt{OPT})),
where n is the number of candidates, OPT is the cost of the optimal ranking,
and O* hides polynomial factors. This is a dramatic improvement on the
previously best known runtime of O*(2^O(OPT)). For feedback arc set tournament
we give an algorithm with runtime O*(2^O(sqrt{OPT})), an improvement on the
previously best known O*(OPT^O(sqrt{OPT})) (Alon, Lokshtanov and Saurabh 2009).
For betweenness tournament we give an algorithm with runtime
O*(2^O(sqrt{OPT/n})), where n is the number of vertices and OPT is the optimal
cost. This improves on the previously known O*(OPT^O(OPT^{1/3}))$ (Saurabh
2009), especially when OPT is small. Unusually we can solve instances with OPT
as large as n (log n)^2 in polynomial time!

我们研究了三个问题的固定参数算法：Kemeny 排名聚合、反馈弧集锦标赛和在两点之间的锦标赛。