Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18012
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKasouridis, Stylianos-
dc.date.accessioned2021-07-15T10:02:52Z-
dc.date.available2021-07-15T10:02:52Z-
dc.date.issued2021-07-09-
dc.identifier.urihttp://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18012-
dc.description.abstractΘεωρούμε την επίδραση ετερογενών αντικειμένων, τοποθετημένων σε διάφορες τοποθεσίες σε ένα δίκτυο, σε γειτονικά αντικείμενα ή οντότητες. Εισάγουμε και μελετάμε ένα μοντέλο, στο οποίο αντικείμενα με υψηλή αξία ασκούν θετική εξωτερική επίδραση σε γειτονικά αντικείμενα με μικρότερη αξία. Στόχος είναι η μεγιστοποίηση αυτής της θετικής επίδρασης, την οποία ονομά- ζουμε συνολική εξωτερική επίδραση στο γράφημα. Αρχικά αποδεικνύουμε ότι το πρόβλημα είναι NP-hard, όταν ο μέγιστος βαθμός είναι 3, αξιο- ποιώντας τη σχέση με το πρόβλημα του ελάχιστου κυρίαρχου συνόλο (minimum dominating set). Στη συνέχεια, δείχνουμε ότι το πρόβλημα είναι επιλύσιμο σε πολυωνυμικό χρόνο όταν ο μέγιστος βαθμός είναι 2. Επιπλέον παρουσιάζουμε αποδοτικούς ακριβείς και προσεγγιστικούς αλγορίθμους για διάφορες ειδικές περιπτώσεις και τοπολογίες. Συγκεκριμένα, δείχνουμε ότι αν υπάρχουν μόνο δύο διαφορετικές πιθανές αξίες αντικειμένων, τότε μια φυσιολογική άπληστη στρατηγική, η οποία πετυχαίνει καλά αποτελέσματα για προβλήματα μέγιστης κάλυψης, οδηγεί σε ένα προσεγγιστικό αλγόριθμο με σταθερό λόγο προσέγγισης. Διεξάγουμε εκτεταμένα αριθμητικά πειράματα, μέσω των οποίων δείχνουμε ότι ο άπληστος αλ- γόριθμος πετυχαίνει πολύ καλά αποτελέσματα για τη γενική περίπτωση του προβλήματος. Θε- ωρούμε περαιτέρω γενικεύσεις του προβλήματος σε άλλα μοντέλα εξωτερικής επίδρασης και αξιολογούμε την άπληστη προσέγγιση σε αυτές τις πιο γενικές περιπτώσεις.en_US
dc.languageenen_US
dc.subjectαλγοριθμική θεωρίαen_US
dc.subjectθεωρία γραφημάτωνen_US
dc.subjectεξωτερικές επιδράσειςen_US
dc.subjectκαλύψειςen_US
dc.subjectκυρίαρχο σύνολοen_US
dc.subjectυπολογιστική πολυπλοκότηταen_US
dc.subjectπροηγμένα θέματα αλγορίθμωνen_US
dc.subjectπροσεγγιστικοί αλγόριθμοιen_US
dc.subjectπειραματική αξιολόγηση αλγορίθμωνen_US
dc.titleΑνάθεση Αντικειμένων και Εξωτερικές Επιδράσεις σε Γράφουςen_US
dc.description.pages90en_US
dc.contributor.supervisorΠαγουρτζής Αριστείδηςen_US
dc.departmentΤομέας Τεχνολογίας Πληροφορικής και Υπολογιστώνen_US
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
Kasouridis_Thesis.pdf432.12 kBAdobe PDFView/Open


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