Academic Bibliography

 Search 200 years of publications by Ghent University researchers.
Advanced search
1 file | 899.13 KB
Add to list
  1. Search results
  2. Solving the Kemeny ranking aggregatio...

Solving the Kemeny ranking aggregation problem with quantum optimization algorithms

Elías F. Combarro, Raul Perez Fernandez (UGent) , José Ranilla and Bernard De Baets (UGent)
(2023) MATHEMATICAL METHODS IN THE APPLIED SCIENCES. 46(16). p.17065-17081
Author
Organization
Project
Abstract
The aim of a ranking aggregation problem is to combine several rankings into a single one that best represents them. A common method for solving this problem is due to Kemeny and selects as the aggregated ranking the one that minimizes the sum of the Kendall distances to the rankings to be aggregated. Unfortunately, the identification of the said ranking-called the Kemeny ranking-is known to be a computationally expensive task. In this paper, we study different ways of computing the Kemeny ranking with quantum optimization algorithms, and in particular, we provide some alternative formulations for the search for the Kemeny ranking as an optimization problem. To the best of our knowledge, this is the first time that this problem is addressed with quantum techniques. We propose four different ways of formulating the problem, one novel to this work. Two different quantum optimization algorithms-Quantum Approximate Optimization Algorithm and Quantum Adiabatic Computing-are used to evaluate each of the different formulations. The experimental results show that the choice of the formulation plays a big role on the performance of the quantum optimization algorithms.
Keywords
General Engineering, General Mathematics, ranking aggregation, quantum computing, quantum annealing, QAOA

Downloads

  • Download
    Solving the Kemeny ranking aggregation problem wit.pdf
    • full text (Published version)
    • |
    • open access
    • |
    • PDF
    • |
    • 899.13 KB

Citation

Please use this url to cite or link to this publication:

MLA
Combarro, Elías F., et al. “Solving the Kemeny Ranking Aggregation Problem with Quantum Optimization Algorithms.” MATHEMATICAL METHODS IN THE APPLIED SCIENCES, vol. 46, no. 16, Wiley, 2023, pp. 17065–81, doi:10.1002/mma.9489.
APA
Combarro, E. F., Perez Fernandez, R., Ranilla, J., & De Baets, B. (2023). Solving the Kemeny ranking aggregation problem with quantum optimization algorithms. MATHEMATICAL METHODS IN THE APPLIED SCIENCES, 46(16), 17065–17081. https://doi.org/10.1002/mma.9489
Chicago author-date
Combarro, Elías F., Raul Perez Fernandez, José Ranilla, and Bernard De Baets. 2023. “Solving the Kemeny Ranking Aggregation Problem with Quantum Optimization Algorithms.” MATHEMATICAL METHODS IN THE APPLIED SCIENCES 46 (16): 17065–81. https://doi.org/10.1002/mma.9489.
Chicago author-date (all authors)
Combarro, Elías F., Raul Perez Fernandez, José Ranilla, and Bernard De Baets. 2023. “Solving the Kemeny Ranking Aggregation Problem with Quantum Optimization Algorithms.” MATHEMATICAL METHODS IN THE APPLIED SCIENCES 46 (16): 17065–17081. doi:10.1002/mma.9489.
Vancouver
1.
Combarro EF, Perez Fernandez R, Ranilla J, De Baets B. Solving the Kemeny ranking aggregation problem with quantum optimization algorithms. MATHEMATICAL METHODS IN THE APPLIED SCIENCES. 2023;46(16):17065–81.
IEEE
[1]
E. F. Combarro, R. Perez Fernandez, J. Ranilla, and B. De Baets, “Solving the Kemeny ranking aggregation problem with quantum optimization algorithms,” MATHEMATICAL METHODS IN THE APPLIED SCIENCES, vol. 46, no. 16, pp. 17065–17081, 2023.
@article{01HDK8VCKM3JQJHSZS0CH09K1G,
  abstract     = {{The aim of a ranking aggregation problem is to combine several rankings into a single one that best represents them. A common method for solving this problem is due to Kemeny and selects as the aggregated ranking the one that minimizes the sum of the Kendall distances to the rankings to be aggregated. Unfortunately, the identification of the said ranking-called the Kemeny ranking-is known to be a computationally expensive task. In this paper, we study different ways of computing the Kemeny ranking with quantum optimization algorithms, and in particular, we provide some alternative formulations for the search for the Kemeny ranking as an optimization problem. To the best of our knowledge, this is the first time that this problem is addressed with quantum techniques. We propose four different ways of formulating the problem, one novel to this work. Two different quantum optimization algorithms-Quantum Approximate Optimization Algorithm and Quantum Adiabatic Computing-are used to evaluate each of the different formulations. The experimental results show that the choice of the formulation plays a big role on the performance of the quantum optimization algorithms.}},
  author       = {{Combarro, Elías F. and Perez Fernandez, Raul and Ranilla, José and De Baets, Bernard}},
  issn         = {{0170-4214}},
  journal      = {{MATHEMATICAL METHODS IN THE APPLIED SCIENCES}},
  keywords     = {{General Engineering,General Mathematics,ranking aggregation,quantum computing,quantum annealing,QAOA}},
  language     = {{eng}},
  number       = {{16}},
  pages        = {{17065--17081}},
  publisher    = {{Wiley}},
  title        = {{Solving the Kemeny ranking aggregation problem with quantum optimization algorithms}},
  url          = {{http://doi.org/10.1002/mma.9489}},
  volume       = {{46}},
  year         = {{2023}},
}
Altmetric
View in Altmetric
Web of Science
Times cited: