On bottleneck assignment problems under categorization

摘要

In this note we consider two types of bottleneck assignment problems under categorization and show that the problems are strongly NP-hard. Further, it is observed that the algorithms developed in Agarwal and Tikekar (Comput. Oper. Res. 13 (1986) 11) for these problems are of pseudo-polynomial complexity. Thus contrary to what is reported in Agarwal and Tikekar (1986), these algorithms do not guarantee exact optimality of the solutions produced, unless P = NP. Scope and purpose: In this note we point out that the algorithms suggested in Agarwal and Tikekar (1986) to solve the bottleneck assignment problem under categorization (two variations) do not guarantee the optimality of the solution produced, contrary to what is claimed in the paper. However, for applications where a guaranteed optimal solution is not required, the algorithm of Agarwal and Tikekar (1986) may be used as a good heuristic.