Optimality Properties of a Special Assignment Problem

In this paper, it is shown that if the cost matrix of an assignment problem has the following property c_ij = |j − i| then any basic feasible solution is optimal if and only if its unit components belong to two well-defined symmetric regions. The matrix with above mentioned property is called the “reordering matrix,” because it arose for the first time in the reordering of nodes of a critical path and other acyclic network problems. One deals with similar matrices in some problems related to order statistics.