Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17609
Τίτλος: | Αλγόριθμοι Χωρίς Μνήμη για το Γενικευμένο Πρόβλημα των k-Εξυπηρετητών σε Ομοιόμορφους Μετρικούς Χώρους |
Συγγραφείς: | Χρήστου, Δημήτριος Φωτάκης Δημήτριος |
Λέξεις κλειδιά: | Online Αλγόριθμοι Γενικευμένο Πρόβλημα k-Εξυπηρετητών Αλγόριθμοι Χωρίς Μνήμη |
Ημερομηνία έκδοσης: | 13-Ιου-2020 |
Περίληψη: | Το γενικευμένο πρόβλημα των k-εξυπηρετητών είναι μία σημαντική γενίκευση του προβλήματος των k-εξυπηρετητών, το οποίο αποτελεί ένα από τα πιο θεμελιώδη προβλήματα της θεωρίας των online αλγορίθμων. Αν και το πρόβλημα των k-εξυπηρετητών έχει μελετηθεί και κατανοηθεί εκτενώς τις τελευταίες δεκαετίες, το γενικευμένο πρόβλημα των k-εξυπηρετητών έχει γίνει κατανοητό σε πολύ μικρότερο βαθμό, με τα περισσότερα σχετικά αποτελέσματα να αφορούν μόνο ειδικές περιπτώσεις μετρικών χώρων. Στόχος της παρούσας διπλωματικής εργασίας είναι η μελέτη του γενικευμένου προβλήματος των k-εξυπηρετητών σε ομοιόμορφους μετρικούς χώρους. Παρακινούμενοι από την αντιστάθμιση ανάμεσα στον λόγο ανταγωνιστικότητας και στην υπολογιστική αποτελεσματικότητα των αλγορίθμων, μελετάμε την ισχύ των αλγορίθμων χωρίς μνήμη και δείχνουμε σφιχτά φράγματα της τάξης Θ(k!) για τον λόγο ανταγωνιστικότητάς τους. Συγκεκριμένα, δείχνουμε ότι ο Αρμονικός αλγόριθμος πετυχαίνει αυτόν τον λόγο και αποδεικνύουμε αντίστοιχα κάτω φράγματα. Αυτό το αποτέλεσμα βελτιώνει το διπλά εκθετικό φράγμα των Chiplunkar και Vishwanathan για την πιο γενική περίπτωση των ομοιόμορφων μετρικών χώρων με διαφορετικά βάρη. |
URI: | http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17609 |
Εμφανίζεται στις συλλογές: | Διπλωματικές Εργασίες - Theses |
Αρχεία σε αυτό το τεκμήριο:
Αρχείο | Περιγραφή | Μέγεθος | Μορφότυπος | |
---|---|---|---|---|
Thesis.pdf | 828.23 kB | Adobe PDF | Εμφάνιση/Άνοιγμα |
Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.