Αποδοτική Χωροθέτηση Σημείων Συγκέντρωσης σε Δίκτυα Ιδιοτελούς Δρομολόγησης

Abstract

Σε αυτή την διπλωματική θα μας απασχολήσει ένα καινούργιο πρόβλημα που συνδυάζει τους τομείς της Χωροθέτησης Εγκαταστάσεων και των Παιγνίων Συμφόρησης. Ονομάζουμε το πρόβλημα Χωροθέτηση Εγκαταστάσεων για Ιδιοτελής Χρήστες και το εξετάζουμε τόσο από την σκοπιά της βελτιστοποίησης όσο και από την σκοπιά της Θεωρίας Παιγνίων. Έχοντας εξετάσει την υπάρχουσα διεθνή βιβλιογραφία πάνω στα προβλήματα Χωροθέτησης Εγκαταστάσεων, Σχεδίασης Δικτύων και Παιγνίων Συμφόρησης, εφαρμόζουμε την γνώση αυτή πάνω σε διαφορετικές εκδοχές του προβλήματος μας. Η συνεισφορά της παρούσας εργασίας είναι πολυεπίπεδη. Μέσω αντιπαραδειγμάτων δείχνουμε πως και γιατί οι γνωστές τεχνικές τοπικής αναζήτησης και γραμμικού προγραμματισμού αποτυγχάνουν να μας δώσουν καλές προσεγγιστικές λύσεις. Μελετώντας την δομή της βέλτιστης λύσης περιορίζουμε τον χώρο αναζήτησης βέλτιστων λύσεων. Παρουσιάζουμε έναν αλγόριθμο με λογαριθμικό λόγο προσέγγισης για μια εκδοχή του γενικού προβλήματος. Στρεφόμενοι στην παιγνιοθεωρητική όψη, βρίσκουμε προσεγγιστικές ισορροπίες και φράσσουμε το τίμημα της αναρχίας. Τέλος, εφαρμόζοντας τεχνικές αραίωσης δίνουμε μια προσεγγιστική λύση για μια απλή εκδοχή του προβλήματος δείχνοντας παράλληλα γιατί η εφαρμογή τέτοιων τεχνικών αποτυγχάνει στο γενικό πρόβλημα.