| Περίληψη: | Στην παρούσα διπλωματική εργασία, ασχολούμαστε με το πρόβλημα της συνάθροισης κατατάξεων
(rank aggregation). Στο πρόβλημα αυτό, βασικός στόχος είναι ο υπολογισμός μιας πλήρους κατάτα-
ξης εναλλακτικών επιλογών, συνδυάζοντας διαφορετικές κατατάξεις. Οι βασικές αλγοριθμικές τεχνικές
που έχουν χρησιμοποιηθεί για τη λύση του προβλήματος προέρχονται από τη Θεωρία της Κοινωνικής
Επιλογής και αποτελούν εφαρμογές κανόνων βαθμολόγησης θέσης (positional scoring rules). Οι γνω-
στές εφαρμογές κανόνων ψηφοφορίας υποθέτουν ότι οι κατατάξεις που χρησιμοποιούνται ως είσοδος
είναι πλήρεις (δηλαδή, αποτελούν κατατάξεις όλων των εναλλακτικών επιλογών). Σε αντίθεση με τα
προβλήματα που έχουν μελετηθεί στη βιβλιογραφία, εμείς μελετάμε το πρόβλημα της συνάθροισης με
είσοδο ελλιπείς κατατάξεις (δηλαδή, κατατάξεις επί υποσυνόλων των εναλλακτικών επιλογών). Στο συ-
γκεκριμένο πρόβλημα θεωρούμε επίσης ότι παίρνουμε σαν είσοδο και ένα σύνολο επιθυμητών σχέσεων
μεταξύ ζευγαριών εναλλακτικών επιλογών οι οποίες δεν είναι όλες το ίδιο σημαντικές. Αυτό το σενά-
ριο μπορεί να βρει πλήθος εφαρμογών στην πράξη, κυρίως σε εφαρμογές τύπου crowdsourcing. Εμείς
εστιάζουμε συγκεκριμένα στο αντίστοιχο πρόβλημα βελτιστοποίησης, σχεδιάζοντας και αναλύοντας αλ-
γορίθμους οι οποίοι υπολογίζουν βέλτιστους κανόνες βαθμολόγησης. Επιπροσθέτως, σε μία προσπάθεια
να βελτιώσουμε το χρόνο εύρεσης του βέλτιστου κανόνα βαθμολόγησης, μελετάμε το πρόβλημα και από
τη σκοπιά των προσεγγιστικών αλγορίθμων. Τελειώνοντας, εμπλουτίζουμε τα θεωρητικά μας αποτελέ-
σματα με πειραματικά αποτελέσματα που διεξάγαμε πάνω σε ελλιπείς κατατάξεις που συλλέξαμε καθώς
και σε ελλιπείς κατατάξεις που κατασκευάσαμε με τη χρήση θεωρητικών μοντέλων θορύβου.
|
|---|
