An analysis of a decomposition heuristic for the assignment problem (Q1062912)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An analysis of a decomposition heuristic for the assignment problem |
scientific article |
Statements
An analysis of a decomposition heuristic for the assignment problem (English)
0 references
1985
0 references
\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.
0 references
performance analysis
0 references
analysis of algorithms
0 references
decomposition
0 references
approximate solutions
0 references
assignment problem
0 references
heuristic solution
0 references