{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1321458"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1321458","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Variants of stable marriage, algorithms, complexity and structural properties","abstract":"Το πρόβλημα του Σταθερού Γάμου, προτάθηκε το 1962 από τους David Gale και Lloyd Sharpley. Από τότε, έχουν υπάρξει πολλά θεωρητικά αποτελέσματα αλλά και πολλές εφαρμογές. Επίσης, έχουν προταθεί αρκετές παραλλαγές του προβλήματος, δημιουργώντας μία πολύ ενδιαφέρουσα κλάση προβλημάτων. Η διπλωματική αυτή είναι μία επισκόπηση της βιβλιογραφίας, σχετικά με το πρόβλημα του Σταθερού Γάμου και των παραλλαγών του και, επικεντρώνεται στα αλγοριθμικά αποτελέσματα αλλά και στα αποτελέσματα πολυπλοκότητας και δομής που έχουν δημοσιευτεί ως τώρα. Επιπλέον, ένα καινούριο αποτέλεσμα παρουσιάζεται. Συγκεκριμένα, υπολογίζεται ένα άνω φράγμα για το μέγιστο πλήθος σταθερών ταιριασμάτων για το πρόβλημα του Σταθερού Γάμου και, μέσω αναγωγών αυτό το φράγμα επεκτείνεται στα προβλήματα Hospital-Residents και Stable Roommates.","abstract_html":"Το πρόβλημα του Σταθερού Γάμου, προτάθηκε το 1962 από τους David Gale και Lloyd Sharpley. Από τότε, έχουν υπάρξει πολλά θεωρητικά αποτελέσματα αλλά και πολλές εφαρμογές. Επίσης, έχουν προταθεί αρκετές παραλλαγές του προβλήματος, δημιουργώντας μία πολύ ενδιαφέρουσα κλάση προβλημάτων. Η διπλωματική αυτή είναι μία επισκόπηση της βιβλιογραφίας, σχετικά με το πρόβλημα του Σταθερού Γάμου και των παραλλαγών του και, επικεντρώνεται στα αλγοριθμικά αποτελέσματα αλλά και στα αποτελέσματα πολυπλοκότητας και δομής που έχουν δημοσιευτεί ως τώρα. Επιπλέον, ένα καινούριο αποτέλεσμα παρουσιάζεται. Συγκεκριμένα, υπολογίζεται ένα άνω φράγμα για το μέγιστο πλήθος σταθερών ταιριασμάτων για το πρόβλημα του Σταθερού Γάμου και, μέσω αναγωγών αυτό το φράγμα επεκτείνεται στα προβλήματα Hospital-Residents και Stable Roommates.","abstract_has_math":false,"creators":["Σταθόπουλος Γεώργιος"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011","date_published":"2011","updated_at":"2026-11-19T05:26:43Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321458"],"render_values":[{"text":"uoadl:1321458","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321458","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321458","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1321458","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Σταθόπουλος Γεώργιος"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321458","https://pergamos.lib.uoa.gr/uoa/dl/object/1321458"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Το πρόβλημα του Σταθερού Γάμου, προτάθηκε το 1962 από τους David Gale και Lloyd Sharpley. Από τότε, έχουν υπάρξει πολλά θεωρητικά αποτελέσματα αλλά και πολλές εφαρμογές. Επίσης, έχουν προταθεί αρκετές παραλλαγές του προβλήματος, δημιουργώντας μία πολύ ενδιαφέρουσα κλάση προβλημάτων. Η διπλωματική αυτή είναι μία επισκόπηση της βιβλιογραφίας, σχετικά με το πρόβλημα του Σταθερού Γάμου και των παραλλαγών του και, επικεντρώνεται στα αλγοριθμικά αποτελέσματα αλλά και στα αποτελέσματα πολυπλοκότητας και δομής που έχουν δημοσιευτεί ως τώρα. Επιπλέον, ένα καινούριο αποτέλεσμα παρουσιάζεται. Συγκεκριμένα, υπολογίζεται ένα άνω φράγμα για το μέγιστο πλήθος σταθερών ταιριασμάτων για το πρόβλημα του Σταθερού Γάμου και, μέσω αναγωγών αυτό το φράγμα επεκτείνεται στα προβλήματα Hospital-Residents και Stable Roommates.","Since 1962, when the Stable Marriage Problem was first proposed by David Gale and Lloyd Sharpley, there have been many theoretical results as well as numerous applications. Also, numerous variants of the problem have been proposed, thus establishing a very interesting class of problems. This thesis is a thorough review of the literature, concerning Stable Marriage and its variants, concentrating on the algorithmic, complexity and structural results that have been published so far. Also, a new result is presented, namely, an upper bound on the maximum number of stable matchings for the Stable Marriage problem and, via reductions this bound is extended to the Hospital-Residents and Stable Roommates problems."]},{"key":"dc:title","label":"Title","values":["Variants of stable marriage, algorithms, complexity and structural properties"]}]}],"canonical_facts":{"dc:creator":["Σταθόπουλος Γεώργιος"],"dc:date":["2011"],"dc:description":["Το πρόβλημα του Σταθερού Γάμου, προτάθηκε το 1962 από τους David Gale και Lloyd Sharpley. Από τότε, έχουν υπάρξει πολλά θεωρητικά αποτελέσματα αλλά και πολλές εφαρμογές. Επίσης, έχουν προταθεί αρκετές παραλλαγές του προβλήματος, δημιουργώντας μία πολύ ενδιαφέρουσα κλάση προβλημάτων. Η διπλωματική αυτή είναι μία επισκόπηση της βιβλιογραφίας, σχετικά με το πρόβλημα του Σταθερού Γάμου και των παραλλαγών του και, επικεντρώνεται στα αλγοριθμικά αποτελέσματα αλλά και στα αποτελέσματα πολυπλοκότητας και δομής που έχουν δημοσιευτεί ως τώρα. Επιπλέον, ένα καινούριο αποτέλεσμα παρουσιάζεται. Συγκεκριμένα, υπολογίζεται ένα άνω φράγμα για το μέγιστο πλήθος σταθερών ταιριασμάτων για το πρόβλημα του Σταθερού Γάμου και, μέσω αναγωγών αυτό το φράγμα επεκτείνεται στα προβλήματα Hospital-Residents και Stable Roommates.","Since 1962, when the Stable Marriage Problem was first proposed by David Gale and Lloyd Sharpley, there have been many theoretical results as well as numerous applications. Also, numerous variants of the problem have been proposed, thus establishing a very interesting class of problems. This thesis is a thorough review of the literature, concerning Stable Marriage and its variants, concentrating on the algorithmic, complexity and structural results that have been published so far. Also, a new result is presented, namely, an upper bound on the maximum number of stable matchings for the Stable Marriage problem and, via reductions this bound is extended to the Hospital-Residents and Stable Roommates problems."],"dc:identifier":["uoadl:1321458","https://pergamos.lib.uoa.gr/uoa/dl/object/1321458"],"dc:language":["English"],"dc:title":["Variants of stable marriage, algorithms, complexity and structural properties"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:43Z"}