(A Variation of the Asymmetric Assignment Problem) Consider a problem which is the same as the asymmetric assignment problem with the exception that in a feasible assignment S there can be at most one incident arc for every person and at most one incident arc for every object (that is, there is no need for every person, as well as for every object, to be assigned). The corresponding linear program is
(a) Show that this problem can be converted to an asymmetric assignment problem where all persons must be assigned. Hint: For each person i introduce an artificial object i and a zero cost arc (i, i ).
(b) Adapt and streamline the auction algorithm for asymmetric assignment problems of Section 7.1 to solve the problem.