We study the problem of clustering ranking vectors, where each vector represents preferences as an ordered list of distinct integers. Specifically, we focus on the k-centroids ranking vectors clustering problem (KRC), which aims to partition a set of ranking vectors into k clusters and identify the centroid of each cluster. Unlike classical k-means clustering (KMC), KRC constrains both the observations and centroids to be ranking vectors. We establish the NP-hardness of KRC and characterize its feasible set. For the single-cluster case, we derive a closed-form analytical solution for the optimal centroid, which can be computed in linear time. To address the computational challenges of KRC, we develop an efficient approximation algorithm, KRCA, which iteratively refines initial solutions from KMC, referred to as the baseline solution. Additionally, we introduce a branch-and-bound (BnB) algorithm for efficient cluster reconstruction within KRCA, leveraging a decision tree framework to reduce computational time while incorporating a controlling parameter to balance solution quality and efficiency. We establish theoretical error bounds for KRCA and BnB. Through extensive numerical experiments on synthetic and real-world datasets, we demonstrate that KRCA consistently outperforms baseline solutions, delivering significant improvements in solution quality with fast computational times. This work highlights the practical significance of KRC for personalization and large-scale decision making, offering methodological advancements and insights that can be built upon in future studies.

TECHNICAL NOTE - TN-2023-02-28, FEBRUARY 2023. 1 Abstract This short technical note points out an erroneous claim about a new rule of combination of basic belief assignments presented recently by Kenn et al. in [1], referred as Kenn's rule of combination (or just as KRC for short). We prove thanks a very simple counter-example that Kenn's rule is not associative. Consequently, the results of the method proposed by Kenn et al. highly depends on the ad-hoc sequential order chosen for the fusion process as proposed by the authors. This serious problem casts in doubt the interest of this method and its real ability to provide trustful results and to make good decisions to help for precise breast cancer therapy. Recently a paper devoted to the Breast Cancer Precision Therapy by Kenn et al. [1] attracted our attention for two main reasons: 1) this application of information fusion is very interesting and important; 2) Kenn's et al. method is based on a new rule of combination of basic belief assignments (BBAs).