Άμεσοι Αλγόριθμοι

Abstract

Η παρούσα διπλωματική εργασία εστιάζει στην ερευνητική περιοχή των άμεσων (online) αλγορίθμων, δηλαδή εκείνων που καλούνται να επιλύσουν ένα πρόβλημα βελτιστοποίησης δίχως να έχουν εκ των προτέρων γνώση όλων των σχετικών δεδομένων. Στο πρώτο κεφάλαιο ορίζονται οι βασικές έννοιες της ανταγωνιστικής ανάλυσης, η οποία αποτελεί το πλέον κοινά αποδεκτό κριτήριο αξιολόγησης της επίδοσης άμεσων αλγορίθμων. Ως παράδειγμα εφαρμογής των προηγουμένων, μελετώνται διεξοδικά δύο κλασικά online προβλήματα. Το δεύτερο κεφάλαιο πραγματεύεται τεχνικές σχεδίασης αιτιοκρατικών άμεσων αλγορίθμων. Μάλιστα, έμφαση δίνεται στο σκεπτικό που υποκρύπτεται πίσω από καθεμία τεχνική, το οποίο συνήθως διατυπώνεται ως κάποια «αρχή». Επιπλέον, εξετάζονται οι κυριότερες μέθοδοι ανάλυσης online αλγορίθμων, οι οποίες έχουν χρησιμοποιηθεί ευρέως στη σχετική βιβλιογραφία. Το τρίτο κεφάλαιο ασχολείται με randomized άμεσους αλγορίθμους, οι οποίοι παρουσιάζουν εξαιρετικό ενδιαφέρον διότι η αναμενόμενη επίδοσή τους ως προς την ανταγωνιστική ανάλυση είναι καλύτερη εκείνης των αντίστοιχων αιτιοκρατικών. Τέλος, το τέταρτο κεφάλαιο εστιάζει στο διάσημο πρόβλημα των k-εξυπηρετητών. Συγκεκριμένα, παρατίθενται, αναλύονται και συγκρίνονται ορισμένοι από τους πιο γνωστούς αλγορίθμους που έχουν προταθεί για το πρόβλημα αυτό. Περιγράφεται επίσης η γενικότερη μέθοδος κατασκευής νέων τέτοιων αλγορίθμων μέσω αιτιοκρατικών και ιδίως πιθανοτικών εμφυτεύσεων μετρικών χώρων.