2.6. Kemeny Optimal Aggregation

This function executes Kemeny optimal aggregation. This algorithm identifies the optimal aggregate list as the list which minimizes its distance from all the input preference lists.

Kemeny optimal aggregation is an NP-hard problem with very high computational complexity. It requires the computation of all permutations of the involved input elements and the calculation of the distances (usually by using the Kendall's \(\tau\) metric) of each permutation from all input lists. The brute force solution becomes infeasible when the number of elements gets greater than 15-20, or the number of input lists is greater than 4, so caution is advised.

Function Definitions

void Kemeny(const char inf[], const char relf[], const int evpts,
     const char ranstr[], const char out[])

and

__declspec(dllexport) void __cdecl Kemeny(const char inf[], const char relf[], const int evpts,
     const char ranstr[], const char out[])

Implementation Files

• Kemeny() function: cflagr.cpp and dllflagr.cpp.
• Kemeny optimal aggregation method: src/ram/KemenyOptimal.cpp.

Input arguments

• const char inf[]: The path of the input file that stores the preference lists to be aggregated.
• const char relf[]: The path of the input file that stores the element relevance judgments.
• const int evpts: the elements in the aggregate list on which the evaluation measures (i.e. Precision, and nDCG) will be computed.
• const char ranstr[]: A string that is embedded in the names of the output files. Used when FLAGR is compiled as a shared library.
• const char out[]: The file system location where the output file with the aggregate list will be stored.

Description
The input parameters are parsed and stored in a special C structure called UserParams that is defined in src/InputParams.h. Then, UserParams is passed to the execution driver and the rank aggregation process starts.