Optimality Properties of a Special Assignment Problem

Abstract

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.