On a new algorithm for stable assignment^*

^*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

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:

• Stable assignment problem
• counterexample

C.R. CATEGORIES:

• G.1.6
• 1.6.3

¹Computer Science Department, University of Minnesota, Minneapolis, MN 55455.

²Army 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

¹Computer Science Department, University of Minnesota, Minneapolis, MN 55455.

²Army 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

¹Computer Science Department, University of Minnesota, Minneapolis, MN 55455.

²Army 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