Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17353
Title: Το Άμεσο Πρόβλημα Ελάχιστου Αθροίσματος Κάλυψης Συνόλου
Authors: Βάρδας, Εμμανουήλ
Φωτάκης Δημήτριος
Keywords: Άμεσοι Αλγόριθμοι
Ανταγωνιστική Ανάλυση
Πρόβλημα Ελάχιστου Αθροίσματος Κάλυψης Συνόλου
Πρόβλημα Πρόσβασης Λίστας
Συσσωμάτωση προτιμήσεων
Προβλήματα διάταξης
Issue Date: 29-Aug-2019
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 δεν παρέχουν κάποια εγγύηση υπογραμμικού λόγου ανταγωνισμού. Όλοι αυτοί οι αλγόριθμοι είναι χωρίς μνήμη, δηλαδή οι αποφάσεις τους βασίζονται αποκλειστικά στο σύνολο που έρχεται κάθε φορά και στις θέσεις των στοιχείων του στη λίστα. Καταλήγουμε ότι τέτοιες πρακτικές σχεδιασμού αλγορίθμων χωρίς μνήμη δεν αποδίδουν για το Άμεσο Πρόβλημα Ελάχιστου Αθροίσματος Κάλυψης Συνόλου.
URI: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17353
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
thesis_final_Vardas_Manolis.pdf658.85 kBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.