Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18417
Τίτλος: | Το πρόβλημα μεγιστοποίησης εξωτερικών επιδράσεων από τη σκοπιά της μεγιστοποίησης της διαφοράς μιας submodular και μιας modular συνάρτησης |
Συγγραφείς: | Αϊβασιλιώτης, Παναγιώτης Παγουρτζής Αριστείδης |
Λέξεις κλειδιά: | προσεγγιστικοί αλγόριθμοι submodular συνάρτηση τεχνικές βελτιστοποίησης μη προσεγγισιμότητα μέγιστη κάλυψη προβλήματα κυριαρχίας εξωτερικές επιδράσεις αποσύνθεση |
Ημερομηνία έκδοσης: | 22-Ιου-2022 |
Περίληψη: | Από τις πρώτες κιόλας ερευνητικές μελέτες σε προβλήματα βελτιστοποίησης submodular συναρτήσεων, το συνεχές ενδιαφέρον για τεχνικές βελτιστοποίησης με μεγάλη πρακτική βαρύτητα σε περιοχές με την μεγαλύτερη επιρροή όπως Μηχανική Μάθηση, Αλγοριθμική Θεωρία Παιγνίων, Κοινωνικά Δίκτυα κ.α., έχει κάνει επιτακτική την ανάγκη εύρεσης νέων τρόπων έκφρασης τέτοιων συναρτήσεων. Το ενδιαφέρον μας πηγάζει από μια μελέτη πάνω σε συναρτήσεις της μορφής g = f - c, όπου f είναι μια γ-weakly submodular συνάρτηση που αποτελεί γενίκευση των submodular συναρτήσεων και c μια modular συνάρτηση. Ειδικότερα, θεωρούμε το πρόβλημα μεγιστοποίησης μιας συνάρτησης g = f-c, με την c να είναι συνάρτηση πληθικότητας και την f να αποτελεί την αντικειμενική συνάρτηση μιας οικογένειας προβλημάτων που ορίζουμε ονόματι p-Max k-hop Domination, όπου δοθέντων ενός γραφήματος G και ακεραίων p, k ο στόχος είναι να βρεθεί ένα σύνολο D από p κορυφές του G, έτσι ώστε το σύνολο των κορυφών που βρίσκονται σε απόσταση το πολύ k ακμές από κάποια κορυφή του D, να μεγιστοποιείται. Παρέχουμε μια μέθοδο για να προσεγγίσουμε την βέλτιστη τιμή της g, με διάφορους αλγορίθμους οι οποίοι διαφέρουν ως προς τον τρόπο με τον οποίο αποκτούμε αυτό που αποκαλούμε αποσύνθεση ενός στιγμιότυπου. Τα αποτελέσματά μας μπορούν να χρησιμοποιηθούν για να βελτιώσουν τον λόγο προσέγγισης του προβλήματος OPT-EXT(0,1). Στο γενικό πρόβλημα OPT-EXT, δοθέντων ενός γραφήματος και μιας συλλογής αντικειμένων με αξία, ο στόχος είναι να τοποθετήσουμε τα αντικείμενα στις κορυφές ώστε να μεγιστοποιηθεί η συνολική εξωτερική επίδραση. Στην πραγματικότητα, σχετίζουμε το πρόβλημα p-Max 1-hop Domination με το OPT-EXT(0,1) (στο οποίο οι αξίες των αντικειμένων είναι 0 ή 1) και βελτιώνουμε το προηγούμενο λόγο (e-1)/(e+1) στον νέο (6e-5)/(6e+5). Επιπλέον μελετούμε θέματα προσεγγισιμότητας του OPT-EXT με τις γενικές αξίες καθώς και μιας παραλλαγής του OPT-EXT(0,1). Τέλος, σχετικά με το πρόβλημα p-Max K-hop Domination, με σταθερό (fixed) K >= 1, δείχνουμε ότι ο καλύτερος δυνατός λόγος προσέγγισης του είναι (1-1/e), γενικεύοντας το ήδη γνωστό αποτέλεσμα για K = 1. Για την απόδειξη χρησιμοποιούνται ειδικές αναγωγές, ονόματι gap-preserving reductions |
URI: | http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18417 |
Εμφανίζεται στις συλλογές: | Διπλωματικές Εργασίες - Theses |
Αρχεία σε αυτό το τεκμήριο:
Αρχείο | Περιγραφή | Μέγεθος | Μορφότυπος | |
---|---|---|---|---|
aivasiliotis thesis.pdf | 730.98 kB | Adobe PDF | Εμφάνιση/Άνοιγμα |
Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.