A Generalization of the Assignment Problem, and its Application to the Rank Aggregation Problem

Article type: Research Article

Authors: Manea, Florin | Ploscaru, Călina

Affiliations: Faculty of Mathematics and Computer Science, University of Bucharest, Academiei 14, 010014, Bucharest, Romania. E-mail: flmanea@funinf.cs.unibuc.ro; calina.ploscaru@gmail.com

Abstract: In this paper we propose a generalization of the Assignment Problem. First, we describe an algorithm, based on network flow techniques, that obtains just one solution of the approached problem; further, we develop an algorithm that is able to find all the solutions. Finally, we discuss how this general form of the Assignment Problem can be applied in solving the Rank Aggregation Problem, in the case of rankings with ties.

Keywords: Assignment Problem, network flow, ranking, Rank Aggregation Problem

Journal: Fundamenta Informaticae, vol. 81, no. 4, pp. 459-471, 2007