Ανάθεση Αντικειμένων και Εξωτερικές Επιδράσεις σε Γράφους

Abstract

Θεωρούμε την επίδραση ετερογενών αντικειμένων, τοποθετημένων σε διάφορες τοποθεσίες σε ένα δίκτυο, σε γειτονικά αντικείμενα ή οντότητες. Εισάγουμε και μελετάμε ένα μοντέλο, στο οποίο αντικείμενα με υψηλή αξία ασκούν θετική εξωτερική επίδραση σε γειτονικά αντικείμενα με μικρότερη αξία. Στόχος είναι η μεγιστοποίηση αυτής της θετικής επίδρασης, την οποία ονομά- ζουμε συνολική εξωτερική επίδραση στο γράφημα. Αρχικά αποδεικνύουμε ότι το πρόβλημα είναι NP-hard, όταν ο μέγιστος βαθμός είναι 3, αξιο- ποιώντας τη σχέση με το πρόβλημα του ελάχιστου κυρίαρχου συνόλο (minimum dominating set). Στη συνέχεια, δείχνουμε ότι το πρόβλημα είναι επιλύσιμο σε πολυωνυμικό χρόνο όταν ο μέγιστος βαθμός είναι 2. Επιπλέον παρουσιάζουμε αποδοτικούς ακριβείς και προσεγγιστικούς αλγορίθμους για διάφορες ειδικές περιπτώσεις και τοπολογίες. Συγκεκριμένα, δείχνουμε ότι αν υπάρχουν μόνο δύο διαφορετικές πιθανές αξίες αντικειμένων, τότε μια φυσιολογική άπληστη στρατηγική, η οποία πετυχαίνει καλά αποτελέσματα για προβλήματα μέγιστης κάλυψης, οδηγεί σε ένα προσεγγιστικό αλγόριθμο με σταθερό λόγο προσέγγισης. Διεξάγουμε εκτεταμένα αριθμητικά πειράματα, μέσω των οποίων δείχνουμε ότι ο άπληστος αλ- γόριθμος πετυχαίνει πολύ καλά αποτελέσματα για τη γενική περίπτωση του προβλήματος. Θε- ωρούμε περαιτέρω γενικεύσεις του προβλήματος σε άλλα μοντέλα εξωτερικής επίδρασης και αξιολογούμε την άπληστη προσέγγιση σε αυτές τις πιο γενικές περιπτώσεις.