Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

Language: English

You searched for subject:(stable marriage problem). Showing records 1 – 3 of 3 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


UCLA

1. Rosenbaum, William Bailey. Distributed Almost Stable Matchings.

Degree: Mathematics, 2016, UCLA

The Stable Marriage Problem (SMP) is concerned with the follow scenario: suppose we have two disjoint sets of agents—for example prospective students and colleges, medical residents and hospitals, or potential romantic partners—who wish to be matched into pairs. Each agent has preferences in the form of a ranking of her potential matches. How should we match agents based on their preferences?We say that a matching is "stable" if no unmatched pair of agents mutually prefer each other to their assigned partners. In their seminal work on the SMP, Gale and Shapley prove that a stable matching exists for any preferences. They further describe an efficient algorithm for finding a stable matching. In this dissertation, we consider the computational complexity of the SMP in the distributed setting, and the complexity of finding “almost stable” matchings. Highlights include (1) communication lower bounds for finding stable and almost stable matchings, (2) a distributed algorithm which finds an almost stable matching in poly-logarithmic time, and (3) hardness of approximation results for three dimensional analogues of the SMP.

Subjects/Keywords: Mathematics; Computer science; Economics; communication complexity; computational complexity; distributed algorithms; stable marriage problem; stable matchings

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Rosenbaum, W. B. (2016). Distributed Almost Stable Matchings. (Thesis). UCLA. Retrieved from http://www.escholarship.org/uc/item/6pr8d66m

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Rosenbaum, William Bailey. “Distributed Almost Stable Matchings.” 2016. Thesis, UCLA. Accessed February 23, 2020. http://www.escholarship.org/uc/item/6pr8d66m.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Rosenbaum, William Bailey. “Distributed Almost Stable Matchings.” 2016. Web. 23 Feb 2020.

Vancouver:

Rosenbaum WB. Distributed Almost Stable Matchings. [Internet] [Thesis]. UCLA; 2016. [cited 2020 Feb 23]. Available from: http://www.escholarship.org/uc/item/6pr8d66m.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Rosenbaum WB. Distributed Almost Stable Matchings. [Thesis]. UCLA; 2016. Available from: http://www.escholarship.org/uc/item/6pr8d66m

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation


University of South Africa

2. Philpin, Elizabeth Mary. Stable matching in preference relationships .

Degree: 2009, University of South Africa

It is the aim of this paper to review some of the work done on stable matching, and on stable marriage problems in particular. Variants of the stable marriage problem will be considered, and the similarities and differences from a mathematical point of view will be highlighted. The correlation between preference and stability is a main theme, and the way in which diluted or incomplete preferences affect stability is explored. Since these problems have a wide range of practical applications, it is of interest to develop useful algorithms for the derivation of solutions. Time-complexity is a key factor in designing computable algorithms, making work load a strong consideration for practical purposes. Average and worst-case complexity are discussed. The number of different solutions that are possible for a given problem instance is surprising, and counter-intuitive. This leads naturally to a study of the solution sets and the lattice structure of solutions that emerges for any stable marriage problem. Many theorems derive from the lattice structure of stable solutions and it is shown that this can lead to the design of more efficient algorithms. The research on this topic is well established, and many theorems have been proved and published, although some published proofs have omitted the detail. In this paper, the author selects some key theorems, providing detailed proofs or alternate proofs, showing the mathematical richness of this field of study. Various applications are discussed, particularly with relevance to the social sciences, although mention is made of applications in computer science, game theory, and economics. The current research that is evident in this subject area, by reference to technical papers in periodicals and on the internet, suggests that it will remain a key topic for some time to come. Advisors/Committee Members: Swanepoel, K. (Prof.) (advisor), Barnard, A. (Prof.) (advisor).

Subjects/Keywords: Stable marriage; Matching algorithms; College admissions problem

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Philpin, E. M. (2009). Stable matching in preference relationships . (Doctoral Dissertation). University of South Africa. Retrieved from http://hdl.handle.net/10500/778

Chicago Manual of Style (16th Edition):

Philpin, Elizabeth Mary. “Stable matching in preference relationships .” 2009. Doctoral Dissertation, University of South Africa. Accessed February 23, 2020. http://hdl.handle.net/10500/778.

MLA Handbook (7th Edition):

Philpin, Elizabeth Mary. “Stable matching in preference relationships .” 2009. Web. 23 Feb 2020.

Vancouver:

Philpin EM. Stable matching in preference relationships . [Internet] [Doctoral dissertation]. University of South Africa; 2009. [cited 2020 Feb 23]. Available from: http://hdl.handle.net/10500/778.

Council of Science Editors:

Philpin EM. Stable matching in preference relationships . [Doctoral Dissertation]. University of South Africa; 2009. Available from: http://hdl.handle.net/10500/778

3. Damianidis, Ioannis. The Stable Marriage Problem : Optimizing Different Criteria Using Genetic Algorithms.

Degree: Business and IT, 2011, University of Borås

“The Stable marriage problem (SMP) is basically the problem of finding a stable matching between two sets of persons, the men and the women, where each person in every group has a list containing every person that belongs to other group ordered by preference. The first ones to discover a stable solution for the problem were D. Gale and G.S. Shapley. Today the problem and most of its variations have been studied by many researchers, and for most of them polynomial time algorithms do not exist. Lately genetic algorithms have been used to solve such problems and have often produced better solutions than specialized polynomial algorithms. In this thesis we study and show that the Stable marriage problem has a number of important real-world applications. It the experimentation, we model the original problem and one of its variations and show the benefits of using genetic algorithms for solving the SMP.”

Program: Magisterutbildning i informatik

Subjects/Keywords: stable marriage problem; genetic algorithm; maximum egalitarian happiness matching; maximizing criteria; Engineering and Technology; Teknik och teknologier

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Damianidis, I. (2011). The Stable Marriage Problem : Optimizing Different Criteria Using Genetic Algorithms. (Thesis). University of Borås. Retrieved from http://urn.kb.se/resolve?urn=urn:nbn:se:hb:diva-20401

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Damianidis, Ioannis. “The Stable Marriage Problem : Optimizing Different Criteria Using Genetic Algorithms.” 2011. Thesis, University of Borås. Accessed February 23, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:hb:diva-20401.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Damianidis, Ioannis. “The Stable Marriage Problem : Optimizing Different Criteria Using Genetic Algorithms.” 2011. Web. 23 Feb 2020.

Vancouver:

Damianidis I. The Stable Marriage Problem : Optimizing Different Criteria Using Genetic Algorithms. [Internet] [Thesis]. University of Borås; 2011. [cited 2020 Feb 23]. Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:hb:diva-20401.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Damianidis I. The Stable Marriage Problem : Optimizing Different Criteria Using Genetic Algorithms. [Thesis]. University of Borås; 2011. Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:hb:diva-20401

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.