2-μερή και πολύ-μερή ευσταθή ταιριάσματα: δομές, αλγόριθμοι και εφαρμογές

Περίληψη

Η διατριβή αυτή εξετάζει το πρόβλημα του Ευσταθούς Ταιριάσματος (ET), της Ευσταθούς Εισαγωγής (ΕΕ), του πολλά-προς-πολλά Ευσταθούς Ταιριάσματος (ΊΊΠ) και της Ευσταθούς Εφοδιαστικής Αλυσίδας (ΕΕΑ). Στα πλαίσια του ET, παρέχεται ένας χρονικά βέλτιστος αλγόριθμος που αναγνωρίζει ποια από τα μη ευσταθή ζεύγη μπορούν να αφαιρεθούν από τις λίστες προτίμησης χωρίς να προκαλέσουν αλλαγές στο σύνολο των λύσεων. Επιπλέον, χρησιμοποιώντας ένα κατευθυνόμενο γραμμογράφημα και το μειωμένο γράφημα περιστροφών, δίνεται η ελάχιστη περιγραφή του πολυτόπου του ET. Επιπλέον, η διάσταση του αποδεικνύεται ότι είναι ίση με τον αριθμό των περιστροφών, ενώ υπολογίζεται και η διάμετρος του. Ακόμα, εξετάζεται και η εναλλακτική αναπαράσταση του πολυτόπου αυτού που βασίζεται στις περιστροφές. Επίσης, οι περιστροφές ορίζονται στα πλαίσια του ΕΕ, όπου δίνεται ένας χρονικά βέλτιστος αλγόριθμος για την αναγνώριση όλων των περιστροφών και των μη ευσταθών ζευγών. Ο αλγόριθμος αυτός επεκτείνεται και στην περίπτωση του ΠΠ ...
περισσότερα

Περίληψη σε άλλη γλώσσα

This thesis examines the Stable Matching problem (SM) and some of its most important variants, namely the Stable Admissions (SAX the many-to-many Stable Matching (MM), and the Chain Stable Network problem. In the context of the SM, a time-optimal algorithm is provided that identifies which of the non-stable pairs can be removed from the agents' preference lists without altering the set of solutions. Then, using a directed line-graph to represent the SM, a sparse description of the SM polytope is derived. This description is further reduced to obtain the minimal one by identifying the minimal equation system and the facets of the corresponding polytope. Also, the dimension of the SM polytope is proved to be equal to the number of rotations, while its diameter is also established. Moreover, the alternative rotation-based representation of the SM polytope is also examined. Further, rotations are defined in the SA setting and a time-optimal algorithm for identifying all rotations and all n ...
περισσότερα

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/22841
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/22841
ND
22841
Εναλλακτικός τίτλος
2-sided and multi-sided stable matchings: structures, algorithms, and applications
Συγγραφέας
Ειρηνάκης, Παύλος του Παντελής
Ημερομηνία
2010
Ίδρυμα
Οικονομικό Πανεπιστήμιο Αθηνών. Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Εξεταστική επιτροπή
Μηλιώτης Παναγιώτης
Μάγος Δημήτριος
Μούρτος Ιωάννης
Δουκίδης Γεώργιος
Ζωγράφος Κωνσταντίνος
Κατερίνης Παναγιώτης
Φωτάκης Δημήτριος
Επιστημονικό πεδίο
Κοινωνικές Επιστήμες
Οικονομικά και Επιχειρήσεις
Λέξεις-κλειδιά
Ευστάθεια; Ευσταθής γάμος; Ευσταθής εισαγωγή; Ευσταθής εφοδιαστική αλυσίδα; Προγραμματισμός περιορισμών; Αλγοριθμικη ανάλυση; Πολυεδρική ανάλυση; Περιστροφή
Χώρα
Ελλάδα
Γλώσσα
Αγγλικά
Άλλα στοιχεία
xi, 174 σ., εικ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Σχετικές εγγραφές (με βάση τις επισκέψεις των χρηστών)