拟阵应用于最优分派问题

THE APPLICATION OF MATROID TO THE OPTIMAL ASSIGNMENT PROBLEM

拟阵理论是近年来走在前列的组合数学的一个分支.本文证明了:设x是带有线性序的工作集合,A是“可分派子集”的集合,则(X,R)是个拟阵,从而可用贪婪算法解决运筹学中广义的分派问题.

Matroid theory is a branch of Combinatorial mathematics whichhas come to the fore in the last few years. This paper gives a proof: Let X is a set ofjobs with a linear orderina, R is the collection of the assignable subsets. then (X.R) is a matroid, and therefore the Greed algorithm can be applied to solve the gen-eralized assignment problem of Operations research.