 |
ΌΝΟΜΑ ΕΡΕΥΝΗΤΗ: Γεωργίου Κωνσταντίνος
ΤΙΤΛΟΣ ΔΙΑΤΡΙΒΗΣ: Άμεσοι Αλγόριθμοι και Θεωρία Παιγνίων
ΕΠΙΣΤΗΜΟΝΙΚΕΣ ΠΕΡΙΟΧΕΣ:
- Αλγοριθμική Θεωρεία Παιγνίων και Δικτύων
ΣΥΜΒΟΥΛΕΥΤΙΚΗ ΕΠΙΤΡΟΠΗ:
- Επιβλέπων: Κουτσουπιάς Ηλίας
- Σύμβουλος: Ζησιμόπουλος Βασίλειος
- Σύμβουλος: Κολλιόπουλος Σταύρος
ΣΥΝΤΟΜΗ ΠΕΡΙΓΡΑΦΗ:
Ενδιαφερόμαστε για ένα άμεσο πρόβλημα γνωστό ως carpool scheduling. Σε αυτό το πρόβλημα μια ομάδα n παιχτών σχηματίζουν μια κοινοπραξία αγοράζοντας ένα κοινό μεταφορικό μέσο. Κάθε μέρα ένα υποσύνολο από αυτούς εμφανίζεται και επιθυμεί να μεταβεί σε ένα προκαθορισμένο και πάντα ίδιο μέρος. Πρέπει να επινοηθεί ένας αλγόριθμος που θα αποφασίζει σε πραγματικό χρόνο για το ποιος θα οδηγήσει. Οι λύση που προσφέρει ένας αλγόριθμος αναλύεται με σύμφωνα με την αδικία που προκαλεί και που ορίζεται με τη βοήθεια της Θεωρίας Παιγνίων. Είναι γνωστό ότι κάθε ντετερμινιστικός αλγόριθμος προκαλεί αδικία Θ(n) ενώ είναι πρόκληση να βρεθεί ο βέλτιστος πιθανοτικός αλγόριθμος που γνωρίζουμε οτι έχει αδικία από Ω((logn)^1/3) έως και O(sqrt(nlogn)).
Επίσης ενδιαφερόμαστε για κατανεμημένο σχεδιασμό μηχανισμών. Στο πρόβλημα multicast cost sharing, ένας διακεκριμένος κόμβος σε ένα δίκτυο (δένδρο) προσφέρει μια υπηρεσία.Κάθε παίχτης στο δίκτυο καλείται να δηλώσει πόσο επιθυμεί την υπηρεσία. Ένας μηχανσιμός πρέπει εκτος από το να είναι φιλαλήθης, να αποφασίζει ποιο είναι το σύνολο των παιχτών που θα λάβει την υπηρεσία καθώς και πόσο θα πληρώσει κάθε παίχτης σε αυτό. Καλούμαστε να επινοήσουμε μηχανισμούς που θα βελτιώνουν το επικοινωνιακό κόστος τόσο σε δίκτυα με κόστη ακμών σταθερές όσο και με κυρτές συναρτήσεις. Ενδιαφέρουσα ερώτηση παραμένει το ποιός μπορεί να είναι ένας πιθανοτικός κατανεμημένος μηχανισμός.
|
![]](../images/rdcorner.gif){kind=small}