Please use this identifier to cite or link to this item:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17609
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Χρήστου, Δημήτριος | - |
dc.date.accessioned | 2020-07-14T15:47:28Z | - |
dc.date.available | 2020-07-14T15:47:28Z | - |
dc.date.issued | 2020-07-13 | - |
dc.identifier.uri | http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17609 | - |
dc.description.abstract | Το γενικευμένο πρόβλημα των k-εξυπηρετητών είναι μία σημαντική γενίκευση του προβλήματος των k-εξυπηρετητών, το οποίο αποτελεί ένα από τα πιο θεμελιώδη προβλήματα της θεωρίας των online αλγορίθμων. Αν και το πρόβλημα των k-εξυπηρετητών έχει μελετηθεί και κατανοηθεί εκτενώς τις τελευταίες δεκαετίες, το γενικευμένο πρόβλημα των k-εξυπηρετητών έχει γίνει κατανοητό σε πολύ μικρότερο βαθμό, με τα περισσότερα σχετικά αποτελέσματα να αφορούν μόνο ειδικές περιπτώσεις μετρικών χώρων. Στόχος της παρούσας διπλωματικής εργασίας είναι η μελέτη του γενικευμένου προβλήματος των k-εξυπηρετητών σε ομοιόμορφους μετρικούς χώρους. Παρακινούμενοι από την αντιστάθμιση ανάμεσα στον λόγο ανταγωνιστικότητας και στην υπολογιστική αποτελεσματικότητα των αλγορίθμων, μελετάμε την ισχύ των αλγορίθμων χωρίς μνήμη και δείχνουμε σφιχτά φράγματα της τάξης Θ(k!) για τον λόγο ανταγωνιστικότητάς τους. Συγκεκριμένα, δείχνουμε ότι ο Αρμονικός αλγόριθμος πετυχαίνει αυτόν τον λόγο και αποδεικνύουμε αντίστοιχα κάτω φράγματα. Αυτό το αποτέλεσμα βελτιώνει το διπλά εκθετικό φράγμα των Chiplunkar και Vishwanathan για την πιο γενική περίπτωση των ομοιόμορφων μετρικών χώρων με διαφορετικά βάρη. | en_US |
dc.language | en | en_US |
dc.subject | Online Αλγόριθμοι | en_US |
dc.subject | Γενικευμένο Πρόβλημα k-Εξυπηρετητών | en_US |
dc.subject | Αλγόριθμοι Χωρίς Μνήμη | en_US |
dc.title | Αλγόριθμοι Χωρίς Μνήμη για το Γενικευμένο Πρόβλημα των k-Εξυπηρετητών σε Ομοιόμορφους Μετρικούς Χώρους | en_US |
dc.description.pages | 92 | en_US |
dc.contributor.supervisor | Φωτάκης Δημήτριος | en_US |
dc.department | Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών | en_US |
Appears in Collections: | Διπλωματικές Εργασίες - Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Thesis.pdf | 828.23 kB | Adobe PDF | View/Open |
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.