EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3467. On the optimal ranking maximizing a median rank correlation coefficient

Invited abstract in session WD-25: Topics in Combinatorial Optimization II (Contributed), stream Combinatorial Optimization.

Wednesday, 14:30-16:00
Room: 011 (building: 208)

Authors (first author is the speaker)

1. Johan Springael
Engineering Management, University of Antwerp

Abstract

With the abundant availability of data, the importance of proper clustering algorithms has been growing over the past decades. This is even more the case when the objects to be clustered can be represent by either total or partial rankings. A well-known clustering method is the so called k-medoid algorithm. Still the major question remains how to define the median object of a cluster and what is the best one? The similarity measure to adopt in the clustering algorithm when comparing rankings is Kendall’s rank correlation coefficient.
Here we investigate the subproblem of maximizing the median of a set off rank correlation coefficients so as to determine the best median ranking by determining the optimal ranking. Since the optimal median ranking has to be determined, the rank correlation coefficients will also be variable. Hence, the sorting of Kendall’s tau’s in order to determine the median in the optimization model should be incorporated. In case tied rank values are absent, we will show that this optimization problem can be re-written as a linear mathematical program. If however ties are present, the linearization will only be possible if the different possible partitions of the rank values are preprocessed.

Keywords

Status: accepted

Back to the list of papers