Please use this identifier to cite or link to this item: http://hdl.handle.net/10125/9533

Files

File Description SizeFormat 
uhm_phd_9312205_r.pdfVersion for non-UH users. Copying/Printing is not permitted2.51 MBAdobe PDFView/Open
uhm_phd_9312205_uh.pdfVersion for UH users2.48 MBAdobe PDFView/Open

Item Summary

Title: A generalization of the stable marriage algorithms involving group preferences in resource allocation problems
Authors: Li, Zhi Cheng
Issue 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
URI/DOI: http://hdl.handle.net/10125/9533
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.
Appears in Collections:Ph.D. - Communication and Information Sciences
Dissertations



Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.