A linear ordering problem of sets

Juan Aparicio, Mercedes Landete () and Juan F. Monge ()
Additional contact information
Mercedes Landete: University Miguel Hernandez of Elche
Juan F. Monge: University Miguel Hernandez of Elche

Annals of Operations Research, 2020, vol. 288, issue 1, No 2, 45-64

Abstract: Abstract Given a ranking of elements of a set and given a disjoint partition of the same set, the ranking does not generally imply a total order of the partition. In this paper, we introduce the Kendall-$$\tau $$τpartition ranking, a linear order of the subsets of the partition which follows from the given ranking. We prove that, under certain assumptions, the Kendall-$$\tau $$τ partition ranking is robust, in the sense that it remains the same when removing subsets of the partition. Then, we give several results (properties) concerning the adequacy of the ranking for ordering the partition and we prove that the integrality gap of the 0–1 problem associated to the Kendall-$$\tau $$τ partition ranking tends to 8/7. Additionally, we provide a comparison of the new ranking with respect to the mean and median based scores from a theoretical and empirical point of view. Finally, a real application with data from the Programme for International Student Assessment is presented, where countries are ordered based on their school rankings.

Keywords: Linear ordering problem; Rank aggregation problem; Kendall- $$\tau $$ τ distance (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03473-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:288:y:2020:i:1:d:10.1007_s10479-019-03473-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-019-03473-y

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().