Bipartite matchings with specified values for a 0-1 linear function.
Tongnyoul Yi · Deep Blue (University of Michigan) · 1994
Many important applications in engineering require solving an assignment problem so that the solution has a specified value for a given linear function. Unfortunately, even checking the existence of an assignment with a specified value for a linear function is an NP-complete problem. In this dissertation, a special case of this problem in which the coefficients of all the variables in the linear function are either 0 or 1 is considered. When all coefficients are 0 or 1, checking the existence of an assignment with a specified value for the additional linear function can be posed as a matching problem in a bipartite network with colored edges, satisfying an additional constraint on the cardinality of each color in the matching. If all edges corresponding to the coefficient of 1 in the color constraint are colored red and all other edges are colored blue, then the problem becomes one of finding a perfect matching in the bipartite network containing a specified number of red edges. Although the general problem is not easy to solve, some special cases of it can be solved efficiently. An algorithm for finding a perfect matching with required number of red and blue edges in any complete network is presented. The proposed algorithm has a polynomially bounded time complexity $(O(n\sp{2.5})).$ It uses a set of necessary conditions for the nonexistence of a solution, which is also presented here. Also presented are some results on the complexity and other interesting properties of the same problem in incomplete networks.