Online αλγόριθμοι με προβλέψεις

Abstract

Στην παρούσα διπλωματική εργασία μελετάμε online αλγορίθμους με προβλέψεις (learningaugmented online algorithms), δηλαδή, online αλγορίθμους οι οποίοι έχουν πρόσβαση σε ένα μαντείο που κάνει προβλέψεις για το μέλλον. Παρουσιάζουμε τα πιο θεμελιώδη αποτελέσματα τού τομέα καθώς και τις βασικές αρχές που διέπουν την ανάλυση online αλγορίθμων με προβλέψεις. Επιπλέον, εξετάζουμε το πρόβλημα Multistage Matroid Maintenance (MMM) και σχεδιάζουμε online αλγορίθμους με προβλέψεις οι οποίοι έχουν καλύτερη επίδοση από αυτή των κλασικών online αλγορίθμων. Στο πρόβλημα ΜΜΜ καλούμαστε να διατηρήσουμε ένα spanning tree σε ένα δυναμικό γράφημα στο οποίο οι ακμές είναι διαθέσιμες μόνο για συγκεκριμένες χρονικές στιγμές. Στην learning-augmented εκδοχή είμαστε εξοπλισμένοι με ένα μαντείο το οποίο προβλέπει τον χρόνο ζωής κάθε ακμής. Στόχος είναι να αγοράσουμε συνολικά όσο το δυνατόν λιγότερες ακμές. Αναλύουμε τον αλγόριθμο που ακολουθεί τυφλά τις προβλέψεις και δείχνουμε ότι αν οι προβλέψεις είναι ακριβείς ο αλγόριθμος ξεπερνά την απόδοση των κλασικών online αλγορίθμων. Αντίθετα, αν οι προβλέψεις είναι ανακριβείς η απόδοση τού αλγορίθμου είναι εφάμιλλη με αυτή τού βέλτιστου online αλγορίθμου.