Το πρόβλημα μεγιστοποίησης εξωτερικών επιδράσεων από τη σκοπιά της μεγιστοποίησης της διαφοράς μιας submodular και μιας modular συνάρτησης

Abstract

Από τις πρώτες κιόλας ερευνητικές μελέτες σε προβλήματα βελτιστοποίησης 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