Back to Search
Start Over
Solving the Many to Many assignment problem by improving the Kuhn–Munkres algorithm with backtracking.
- Source :
-
Theoretical Computer Science . Mar2016, Vol. 618, p30-41. 12p. - Publication Year :
- 2016
-
Abstract
- The Many to Many (M–M) assignment problem is an important open problem where one task is assigned to many, but different, agents and one agent may undertake many, but different, tasks. The Kuhn–Munkres (K–M) algorithm is a famous and traditional process used in dealing with assignment problems. In this paper, we propose a solution to the M–M assignment problem by improving the K–M algorithm with backtracking (KM B ). To demonstrate the solution's suitability, we prove that the proposed KM B algorithm is valid and that the worst time complexity of the KM B algorithm is O ( ( ∑ L a [ i ] ) 3 ) , where L a [ i ] denotes the maximum number of tasks that can be assigned to agent i . After that, we discuss several critical problems related to the algorithm and provide the necessary and sufficient conditions of solving the M–M assignment problem. Finally, we demonstrate, through experimentation, the validity, practicality and efficiency of the KM B algorithm. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 618
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 112721780
- Full Text :
- https://doi.org/10.1016/j.tcs.2016.01.002