Abstract
The concept of stable assignment comes from a classical assignment problem called the Stable Marriage Assignment. Suppose that there are two disjoint sets, one consists of men and the other of women. Each member of a set ranks the members of the other set in order of preference. Matching persons between two sets is a one-to-one relation. If there does not exist a random pair both preferring each other to their assigned partner, the assignment is said to be stable.
In a recent paper. Huang and Chan generalized the above one-to-one type assignment problem to a multi-function assignment problem and proposed an algorithm for finding stable assignments for both problems. In this paper, we present a couterexample for which the assignment obtained by that algorithm is not stable.
Keywords:
1Computer Science Department, University of Minnesota, Minneapolis, MN 55455.
2Army High Performance Computing Research Center, 1100 Washington Avenue South, Minneapolis, MN 55415. Also from Institute of Operations Research, Qufu Normal University, Qufu, Shandong, PRC.
*This research was supported in part by the Air Force Office of Scientific Research grant AFOSR-87-0127 and a University of Minnesota Doctoral Dissertation Fellowship
1Computer Science Department, University of Minnesota, Minneapolis, MN 55455.
2Army High Performance Computing Research Center, 1100 Washington Avenue South, Minneapolis, MN 55415. Also from Institute of Operations Research, Qufu Normal University, Qufu, Shandong, PRC.
*This research was supported in part by the Air Force Office of Scientific Research grant AFOSR-87-0127 and a University of Minnesota Doctoral Dissertation Fellowship
Notes
1Computer Science Department, University of Minnesota, Minneapolis, MN 55455.
2Army High Performance Computing Research Center, 1100 Washington Avenue South, Minneapolis, MN 55415. Also from Institute of Operations Research, Qufu Normal University, Qufu, Shandong, PRC.
*This research was supported in part by the Air Force Office of Scientific Research grant AFOSR-87-0127 and a University of Minnesota Doctoral Dissertation Fellowship