On solving a variation of the assignment problem

Geetha and Nair recently proposed a variant of n × n assignment problem with the objective of minimizing the total cost plus an additional ‘supervisory’ cost. They gave an O(n⁵) algorithm to solve the problem. Here, we present an algorithm for this problem using Balinski's signature method for the assignment problem at each stage. The algorithm has a complexity of O(m(m+n log n)), where m is the number of arcs in the problem.