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

• Autorzy: Manea F. , Ploscaru C.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Assignment Problem; network flow; ranking; Rank Aggregation Problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 81, nr 4
• Strony: 459--471
• Opis fizyczny: bibliogr. 12 poz.

Twórcy

autor

Manea F.

autor

Ploscaru C.

• University of Bucharest, Faculty of Mathematics and Computer Science, , Str. Academiei 14, 010014, Bucharest, Romania,

Bibliografia

• [1] R. Ahuja, T. Magnanti, J. Orlin, Network Flows, Prentice Hall, Inc., 1993.
• [2] T.H. Cormen, C.E. Leiserson, R.R. Rivest, Introduction to Algorithms, MIT Press, 1990.
• [3] P. Diaconis, Group Representation in Probability and Statistics, IMS Lecture Series 11, IMS, 1988.
• [4] A. Dinu, L. P. Dinu, On the Syllabic Similarities of Romance Languages, LNCS, 3406, 785-788, 2005.
• [5] L. P. Dinu, On the classification and aggregation of hierarchies with different constitutive elements, Fundamenta Informaticae, 55(1), 39-50, 2003.
• [6] L. P. Dinu, Rank Distance with Applications in Similarity of Natural Languages, Fundamenta Informaticae, 64(1-4), 135-149, 2005.
• [7] L.P. Dinu, A. Sgarro, A Low-complexity Distance for DNA Strings, Fundamenta Informaticae, 73(3), 361-372, 2006.
• [8] L.P. Dinu, F. Manea, An efficient approach for the rank aggregation problem, Theoretical Computer Science, 359 (1-3), 455-461, 2006.
• [9] C. Dwork, R. Kumar, M. Naor, and D. Sivakumar,Rank aggregation methods for the web, Proc. of the 10th International WWW Conference, 613-622, ACM, 2001.
• [10] H.W. Kuhn, The Hungarian method for assignment problem, Naval Research Logistics Quarterly, 2, 83-97, 1955.
• [11] F. Manea, C. Ploscaru, Solving a combinatorial problem with network flows, J. of Appl. Math. and Comp., 17(1-2), 391-399, 2005.
• [12] K. Mehlhorn, Graph Algorithms and NP-Completeness, in Data Structures and Algorithms, vol. II, Springer, 1984.