ScholarSpace will be brought offline for upgrades on Wednesday December 9th at 11AM HST. Service will be disrupted for approximately 2 hours. Please direct any questions to

Item Description

Show full item record

Title: A generalization of the stable marriage algorithms involving group preferences in resource allocation problems 
Author: Li, Zhi Cheng
Date: 1992
Abstract: The resource allocation problem usually involves optimization on uniform resources. This thesis solves the problem of finding matchings between several resources and activities which are optimal for a given linear objective function and are stable with regard to preferences of the resources and activities. The concept of a stable matching comes from the stable marriage problem. Given an equal number of men and women, and, for each person, a strictly ordered preference list containing all the members of the opposite sex, a stable marriage is a one-to-one matching of men and women in which there is no man and woman who prefer each other to their partners. Although this stable marriage problem with its strictly ordered preference lists (no ties or indifference) has been studied for three decades in computer science, there are few applications. When arbitrary indifference is allowed, the stable marriage problem has more applications but fails to have some valuable properties such as Pareto Efficiency and majority assignment. We suggest using group preference lists to allow limited indifference in applications. That is, each person belongs to a group that has a preference list for all groups of the opposite sex. We show that with this approach, stability guarantees Pareto Efficiency. We have constructed a correct definition of majority assignment for our case, and show that stability also guarantees majority assignment. For our approach, there is also a polynomial-size representation of all the stable matchings for a given problem. Thus polynomial-time complexity algorithms are possible for optimization over all such matchings. We give algorithms to find the maximal elements in the solution lattice, to find the polynomial-size representation of the solution lattice using rotations, and to find the partial order on the set of rotations. The first two algorithms generalize those of Gale-Shapley and Gusfield. The third one is new. All three algorithms run in O(Np) time, where N is the total number of men or women, p is the number of groups in the other sex. We also develop the lattice structure theory supporting the algorithms.
Description: Thesis (Ph. D.)--University of Hawaii at Manoa, 1992. Includes bibliographical references (leaves 91-92) Microfiche. vii, 92 leaves, bound ill. 29 cm
Rights: All UHM dissertations and theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission from the copyright owner.

Item File(s)

Description Files Size Format View
Restricted for viewing only uhm_phd_9312205_r.pdf 2.455Mb PDF View/Open
For UH users only uhm_phd_9312205_uh.pdf 2.426Mb PDF View/Open

This item appears in the following Collection(s)


Advanced Search


My Account