Show simple item record

Item Description Li, Zhi Cheng en_US 2009-07-15T17:27:41Z en_US 2009-07-15T17:27:41Z en_US 1992 en_US
dc.identifier.uri en_US
dc.description Thesis (Ph. D.)--University of Hawaii at Manoa, 1992. en_US
dc.description Includes bibliographical references (leaves 91-92) en_US
dc.description Microfiche. en_US
dc.description vii, 92 leaves, bound ill. 29 cm en_US
dc.description.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. en_US
dc.language.iso en-US en_US
dc.relation Theses for the degree of Doctor of Philosophy (University of Hawaii at Manoa). Communication and Information Sciences; no. 2824 en_US
dc.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. en_US
dc.title A generalization of the stable marriage algorithms involving group preferences in resource allocation problems en_US
dc.type Thesis en_US
dc.type.dcmi Text en_US

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)

Show simple item record


Advanced Search


My Account