The ``largest element first'' heuristic for the maximization assignment problem (Q1118529)

The standard maximization assignment problem is as follows. Two sets I, J, are given, each with cardinality n. Assigning \(i\in I\) to \(j\in J\) incurs a score \(a_{ij}\). It is required to find a one-one mapping between I and J which has a maximal total score. The ``largest element first'' heuristic selects \((i_ 1,j_ 1)\in \arg\). \(\max_{(i,j)\in I\times J}[a_{ij}]\), \(j_ 1\) is assigned to \(i_ 1\) and \(\{i_ 1,j_ 1\}\) deleted to give \(I_ 1=I-\{i_ 1\}\), \(J_ 1=J-\{j_ 1\}\). The procedure is repeated with \(I_ 1\) and \(J_ 1\), culminating in an assignment. If A is the matrix \(\{a_{ij}\}\), \(H_ n(A)\) a total score achieved by the heuristic, and \(O_ n(A)\) is a maximal score, the paper proves that \(H_ n(A)/O_ n(A)\geq\) and for each \(n\geq 2\), there exists an A such that \(H_ n(A)/O_ n(A)=.\) The above ratios are ``prior'' ratios. The paper also gives expressions for ``posterior ratios''. For a given probability distribution for A, it is proved that \(E_ A(H_ n(A)/O_ n(A))\geq 2/3\).