Το Άμεσο Πρόβλημα Ελάχιστου Αθροίσματος Κάλυψης Συνόλου

Abstract

Στην παρούσα διπλωματική εργασία, μελετάμε το Άμεσο Πρόβλημα Ελάχιστου Αθροίσματος Κάλυψης Συνόλου (Online Min-Sum Set Cover), την άμεση (online) εκδοχή του προβλήματος Ελάχιστου Αθροίσματος Κάλυψης Συνόλου (Min-Sum Set Cover), που προτάθηκε από τους Feige, Lovasz και Tetali. Το πρόβλημα Ελάχιστου Αθροίσματος Κάλυψης Συνόλου μπορεί να χρησιμοποιηθεί στη μοντελοποίηση προβλημάτων διάταξης διαδικτυακών αποτελεσμάτων, όπου αποτελέσματα αναζήτησης ή ενημερώσεις από τα κοινωνικά δίκτυα χρειάζεται να είναι σε διάταξη προσαρμοσμένη στις προτιμήσεις του χρήστη. Τα διαδικτυακά αποτελέσματα μπορούν να θεωρηθούν ως μία λίστα από στοιχεία και οι χρήστες ως σύνολα αυτών των στοιχείων, που προκύπτουν από τις προτιμήσεις τους. Το ζητούμενο του προβλήματος είναι να παραχθεί μία διάταξη της λίστας που να ελαχιστοποιεί το μέσο χρόνο επαφής (hitting time) των συνόλων. Ο χρόνος επαφής ορίζεται ως η θέση του πρώτου στοιχείου στη διάταξη, που βρίσκεται στο σύνολο. Αυτό το πλαίσιο μοντελοποιεί το χρόνο που απαιτείται από ένα χρήστη να σκανάρει τη λίστα αποτελεσμάτων από πάνω προς τα κάτω για να βρει το πρώτο επιθυμητό αποτέλεσμα. Παρ' όλα αυτά, το πρόβλημα Ελάχιστου Αθροίσματος Κάλυψης Συνόλου υποθέτει ότι όλα τα σύνολα δίνονται εξ' αρχής. Ένα ρεαλιστικό σενάριο είναι η παραγόμενη διάταξη αποτελεσμάτων να ανανεώνεται τακτικά, καθώς νέα σύνολα εμφανίζονται έπειτα από ενέργειες που κάνουν οι χρήστες. To Άμεσο Πρόβλημα Ελάχιστου Αθροίσματος Κάλυψης Συνόλου επιχειρεί να επιλύσει αυτό το πρόβλημα υποθέτοντας ότι τα σύνολα έρχονται σταδιακά, με άμεσο (online) τρόπο.

Ένα πιο απλό πρόβλημα, στο οποίο εντοπίζουμε σύνδεση με το πρόβλημα μας είναι το πολύ γνωστό Πρόβλημα Πρόσβασης Λίστας (List Accessing Problem), όπου στοιχεία, και όχι σύνολα, έρχονται online. Η δουλειά μας βασίζεται κυρίως στο πρόβλημα Πρόσβασης Λίστας και στον 2-ανταγωνιστικό (2-competitive) ντετερμινιστικό αλγόριθμο Move-To-Front. Αποδεικνύουμε ένα κάτω φράγμα A+1-A(A+1)/(l+1) για το λόγο ανταγωνισμού (competitive ratio) κάθε ντετερμινιστικού αλγορίθμου, όπου A είναι η μέση πληθικότητα των συνόλων που δίνονται ως είσοδος και l το μήκος της λίστας. Επιπλέον, προτείνουμε τρεις αλγορίθμους εμπνευσμένους από τον αλγόριθμο Move-To-Front, τους MoveFront, MoveLast και MoveSet. Δείχνουμε ότι ο MoveFront είναι (l-A+1)-competitive και οι MoveLast, MoveSet ακριβώς l-competitive. Στην περίπτωση των πιθανοτικών αλγορίθμων, δείχνουμε ότι οι προτεινόμενοι αλγόριθμοι Randomized Static και Randomized Move-To-Front δεν παρέχουν κάποια εγγύηση υπογραμμικού λόγου ανταγωνισμού. Όλοι αυτοί οι αλγόριθμοι είναι χωρίς μνήμη, δηλαδή οι αποφάσεις τους βασίζονται αποκλειστικά στο σύνολο που έρχεται κάθε φορά και στις θέσεις των στοιχείων του στη λίστα. Καταλήγουμε ότι τέτοιες πρακτικές σχεδιασμού αλγορίθμων χωρίς μνήμη δεν αποδίδουν για το Άμεσο Πρόβλημα Ελάχιστου Αθροίσματος Κάλυψης Συνόλου.