An analysis of a decomposition heuristic for the assignment problem (Q1062912)

\textit{J. M. Kurtzberg} [J. Assoc. Comput. Mach. 9, 419-439 (1962; Zbl 0108.333)] proposed a method of obtaining approximate solutions to the assignment problem by decomposing a large problem into many smaller subproblems. Thus a km\(\times km\) assignment problem is decomposed into \(k^ 2\) problems of size \(m\times m\) and one problem of size \(k\times k\). In this paper we analyze the performance of this heuristic, obtaining the following main results: (1) For the maximization problem, the ratio of the optimal solution to the heuristic solution can be as large as, but cannot exceed min(k,m); (2) For the minimization problem, if \(k=O(n/\log n)\) where \(n=mk\), and the matrix elements are independently drawn from a uniform distribution on (0,1), in the limit the expected value of the heuristic solution is at least k/3 times that of the optimal solution.