Πλοήγηση ανά Συγγραφέα "Samaris, Michail"

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω

Τώρα δείχνει 1 - 1 από 1

Optimisation under preferences for matchings and circulations: combinatorial and polyhedral aspects
(2023-10-31) Σάμαρης, Μιχαήλ; Samaris, Michail; Athens University of Economics and Business, Department of Management Science and Technology; Eirinakis, Pavlos; Thilikos, Dimitrios; Giannopoulou, Archontia; Magos, Dimitrios; Markakis, Evangelos; Papadopoulos, Charis; Mourtos, Ioannis
Σε αυτή τη διδακτορική διατριβή εξετάζονται διάφορα προβλήματα βελτιστοποίησης υπό προτιμήσεις που ορίζονται με όρους Θεωρίας Γραφημάτων. Μελετάμε τα προβλήματα αυτά από συνδυαστική, πολυεδρική και αλγοριθμική άποψη. Αυτό που αναφέρουμε ως προτιμήσεις αντιπροσωπεύει εκφρασμένες επιλογές ή πιθανές αποφάσεις για ένα άτομο σε μια διάταξη που απαντά ποια είναι καλύτερη από την άλλη. Πολλά από τα προβλήματα που μελετάμε έχουν χρησιμοποιηθεί για να αναπαραστήσουν πραγματικές καταστάσεις λήψης αποφάσεων για άτομα ή οργανισμούς. Πρώτον, το πρόβλημα του Ευσταθούς Ταιριάσματος (SM), το πρόβλημα του πολλά-προς-πολλά Ευσταθούς Ταιριάσματος (MM) και το πρόβλημα της Ευσταθούς Κατανομής (SA) παρουσιάζονται μαζί με μερικά σημαντικά συνδυαστικά και πολυεδρικά αποτελέσματα σχετικά με αυτά. Δίνεται μια ελαχιστική πολυεδρική περιγραφή για τα SM, MM και την μη περιορισμένη περίπτωση του SA μέσω ενός αφινικού μετασχηματισμού του πολυτόπου διάταξης της διάταξης των περιστροφών τους. Για την μη περιορισμένη περίπτωση του SA είναι η πρώτη φορά που δίνεται μια ελάχιστική περιγραφή. Για να δειχθεί αυτός ο μετασχηματισμός αποδεικνύουμε διάφορα συνδυαστικά αποτελέσματα για τα πρoβληματα αυτά. Στη συνέχεια, αυτή η διατριβή προτείνει έναν νέο τρόπο χαλάρωσης του κριτηριού της Ευστάθειας στο SM, ορίζοντας το Πρόβλημα ασταθούς ταιριάσματος, όπου κάθε ζεύγος έχει μία τιμή κέρδους εάν συμμετέχει στο ταίριασμα και μια τιμή κόστους εάν το μπλοκάρει. Η εύρεση ενός ταιριάσματος που μεγιστοποιεί τη συνάρτηση το κέρδος από τα ζευγάρια που συμμετέχουν σε αυτό μείον το κόστος από τα ζευγάρια που το μπλοκάρουν είναι NP-δύσκολο. Αν η τιμή κέρδους και η τιμή κόστους ταυτίζονται για κάθε ζευγάρι οι περιπτώσεις όπου είτε αυτή η συνάρτηση περιορίζεται στο (0, 1) είτε είναι αύξουσα ως προς τις προτιμήσεις επιλύονται σε πολυωνυμικό χρόνο. Αντίθετα, εάν η συνάρτηση περιορίζεται σε δύο γενικές τιμές (α, β), το πρόβλημα παραμένει NP-hard. Μια άλλη περίπτωση που αποδεικνύεται ότι το πρόβλημα αυτο είναι πολυωνυμικά επιλύσιμο είναι όταν το σύνολο των ζευγαριών διαμερίζεται σε αυτά που μπορούν να αποτελούν μέρος της αντιστοίχισης εξόδου αλλά δεν επιτρέπεται να το μπλοκάρουν (η τιμή κόστους τους είναι +∞) και σε εκείνα που μπορούν να μπλοκάρουν ενα ταίριασμα με κάποιο κόστος, αλλά δεν μπορεί να είναι μέρος του (η τιμή κέρδους τους είναι −∞). Αυτή η διατριβή εξετάζει επίσης μια νέα γενίκευση ενός-προς-πολλά του Παρέτο βέλτιστου ταιριάσματος όπου δεν υπάρχει ανώτατο όριο για το πόσοι συμμετέχοντες μπορούν να λάβουν ένα συγκεκριμένο αγαθό, αλλά υπάρχουν ζεύγη συμμετεχόντων που δεν μπορούν να λάβουν το ίδιο αγαθό. Από μια άλλη οπτική γωνία, αυτή η παραλλαγή του προβλήματος μπορεί να θεωρηθεί ως πρόβλημα χρωματισμού σε ένα γράφημα μεσα απο λίστα προτιμήσεων. Παρόλο που ο μηχανισμός της Σειριακής Δικτατορίας επιστρέφει ένα Παρέτο βέλτιστο χρωματισμό, μέσω αντιπαραδείγματος δείχνουμε οτι το αντίστροφο δεν ισχύει και ότι υπάρχουν Παρέτο βέλτιστοι χρωματισμοί που δεν μπορούν να ληφθούν από την Σειριακή Δικτατορία. Πλέον το πρόβλημα του να αποφασίσουμε εάν ενας δεδομένος χρωματισμός είναι Πάρετο βέλτιστος δεν είναι πλέον εύκολο, αλλά γίνεται coNP-δύσκολο. Σε ορισμένες ειδικές περιπτώσεις παραμένει πολυωνυμικά επιλύσιμο. Το τελευταίο πρόβλημα που μελετήθηκε σε αυτή τη διατριβή είναι ένα προβλημα ανταλλακτικών αγορών με αδιαίρετα αγαθά οπου οι συμμετέχοντες εκφράζουν προτιμήσεις και το κεντρικό κριτήριο που είναι ζητούμενο σε μια ανταλλαγή είναι η Παρέτο βελτιστότητα. Επιστρέφεται μια λύση από τον μηχανισμο Top Trading Cycle και παρέχεται επίσης ένας συνδυαστικός χαρακτηρισμός των Παρέτο βέλτιστων λύσεων. Αυτός ο χαρακτηρισμός οδηγεί άμεσα σε έναν εύκολο τρόπο αναγνώρισης εάν μια δεδομένη ανταλλαγή είναι Παρέτο βέλτιστη. Επιπλέον, αποδεικνύεται ότι εάν υπάρχει συνάρτηση βάρους για την εύρεση πιθανής ανταλλαγής, η ανταλλαγή μέγιστου βάρους είναι NP-δύσκολο. Εάν το βάρος είναι συνάρτηση αύξουσα ως προς τις προτιμήσεις τότε το πρόβλημα λύνεται σε πολυωνυμικό χρόνο.