Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18243
Full metadata record
DC FieldValueLanguage
dc.contributor.authorΝικολάου, Ιάσονας-
dc.date.accessioned2022-03-03T08:31:38Z-
dc.date.available2022-03-03T08:31:38Z-
dc.date.issued2022-03-02-
dc.identifier.urihttp://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18243-
dc.description.abstractΣτην παρούσα διπλωματική εργασία μελετάμε online αλγορίθμους με προβλέψεις (learningaugmented online algorithms), δηλαδή, online αλγορίθμους οι οποίοι έχουν πρόσβαση σε ένα μαντείο που κάνει προβλέψεις για το μέλλον. Παρουσιάζουμε τα πιο θεμελιώδη αποτελέσματα τού τομέα καθώς και τις βασικές αρχές που διέπουν την ανάλυση online αλγορίθμων με προβλέψεις. Επιπλέον, εξετάζουμε το πρόβλημα Multistage Matroid Maintenance (MMM) και σχεδιάζουμε online αλγορίθμους με προβλέψεις οι οποίοι έχουν καλύτερη επίδοση από αυτή των κλασικών online αλγορίθμων. Στο πρόβλημα ΜΜΜ καλούμαστε να διατηρήσουμε ένα spanning tree σε ένα δυναμικό γράφημα στο οποίο οι ακμές είναι διαθέσιμες μόνο για συγκεκριμένες χρονικές στιγμές. Στην learning-augmented εκδοχή είμαστε εξοπλισμένοι με ένα μαντείο το οποίο προβλέπει τον χρόνο ζωής κάθε ακμής. Στόχος είναι να αγοράσουμε συνολικά όσο το δυνατόν λιγότερες ακμές. Αναλύουμε τον αλγόριθμο που ακολουθεί τυφλά τις προβλέψεις και δείχνουμε ότι αν οι προβλέψεις είναι ακριβείς ο αλγόριθμος ξεπερνά την απόδοση των κλασικών online αλγορίθμων. Αντίθετα, αν οι προβλέψεις είναι ανακριβείς η απόδοση τού αλγορίθμου είναι εφάμιλλη με αυτή τού βέλτιστου online αλγορίθμου.en_US
dc.languageenen_US
dc.subjectOnline algorithms, Learning-augmented online algorithms, Online algorithms with predictionsen_US
dc.titleOnline αλγόριθμοι με προβλέψειςen_US
dc.description.pages77en_US
dc.contributor.supervisorΦωτάκης Δημήτριοςen_US
dc.departmentΤομέας Τεχνολογίας Πληροφορικής και Υπολογιστώνen_US
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
Thesis_Iasonas_Nikolaou.pdf377.34 kBAdobe PDFView/Open


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