On the linear assignment problem for special matrices
Peter Butkovič · IMA Journal of Management Mathematics · 2004
This study arises from the intersection of two application areas of management mathematics and control theory: the assignment problem and the theory of discrete‐event dynamic systems (DEDS). The assignment problem is to find the cheapest one‐to‐one pairing between two sets (e.g. machines and operators), given a matrix (aij) of the cost of pairing the ith machine with the jth operator. A DEDS is a system such as certain manufacturing, transportation or data‐processing systems, which move from event to event in discrete steps. The realization problem for such a DEDS is that of deducing its possible structure on the basis of a stream of observations, g0,g1,..., known as Markov parameters. The structure is expressed in a linear‐algebraic model known as a realization and for economy a realization of minimal dimension (MDR) is sought. For certain DEDS, it is convenient to work in max‐algebra, in which the classsical operations of addition and multiplication are replaced by the operations max and +, respectively. Establishing a lower bound for the dimension of an MDR then turns on finding the structure of the optimal solution set of an assignment problem whose cost matrix is a Hankel matrix. This is connected to a known hard combinatorial problem and does not seem to be solved for Hankel matrices in general. However, the paper shows that a straightforward solution exists in two special cases, when the sequence {gr} is either convex or concave.