1. Home page
  2. Search

Facility Location in Selfish Routing Networks

This item is provided by the institution :
National Technical University of Athens   

Repository :
Digital Library of National Technical University of Athens | Dspace@NTUA   

see the original item page
in the repository's web site and access all digital files if the item*



Αποδοτική χωροθέτηση σημείων συγκέντρωσης σε δίκτυα ιδιοτελούς δρομολόγησης (EL)
Facility Location in Selfish Routing Networks (EN)
Μερτζανίδης, Μάριος (EL)
Mertzanidis, Marios (EN)
ntua (EL)
Φωτάκης, Δημήτριος (EL)
Μαρκάκης, Ευάγγελος (EL)
Λιανέας, Θανάσης (EL)
Παγουρτζής, Αριστείδης (EL)
bachelorThesis
2021-11-11
2022-05-18T10:25:27Z
Σε αυτή την διπλωματική θα μας απασχολήσει ένα καινούργιο πρόβλημα που συνδυάζει τους τομείς της Χωροθέτησης Εγκαταστάσεων και των Παιγνίων Συμφόρησης. Ονομάζουμε το πρόβλημα Χωροθέτηση Εγκαταστάσεων για Ιδιοτελής Χρήστες και το εξετάζουμε τόσο από την σκοπιά της βελτιστοποίησης όσο και από την σκοπιά της Θεωρίας Παιγνίων. Έχοντας εξετάσει την υπάρχουσα διεθνή βιβλιογραφία πάνω στα προβλήματα Χωροθέτησης Εγκαταστάσεων, Σχεδίασης Δικτύων και Παιγνίων Συμφόρησης, εφαρμόζουμε την γνώση αυτή πάνω σε διαφορετικές εκδοχές του προβλήματος μας. Η συνεισφορά της παρούσας εργασίας είναι πολυεπίπεδη. Μέσω αντιπαραδειγμάτων δείχνουμε πως και γιατί οι γνωστές τεχνικές τοπικής αναζήτησης και γραμμικού προγραμματισμού αποτυγχάνουν να μας δώσουν καλές προσεγγιστικές λύσεις. Μελετώντας την δομή της βέλτιστης λύσης περιορίζουμε τον χώρο αναζήτησης βέλτιστων λύσεων. Παρουσιάζουμε έναν αλγόριθμο με λογαριθμικό λόγο προσέγγισης για μια εκδοχή του γενικού προβλήματος. Στρεφόμενοι στην παιγνιοθεωρητική όψη, βρίσκουμε προσεγγιστικές ισορροπίες και φράσσουμε το τίμημα της αναρχίας. Τέλος, εφαρμόζοντας τεχνικές αραίωσης δίνουμε μια προσεγγιστική λύση για μια απλή εκδοχή του προβλήματος δείχνοντας παράλληλα γιατί η εφαρμογή τέτοιων τεχνικών αποτυγχάνει στο γενικό πρόβλημα. (EL)
In this thesis, we are preoccupied with solving a novel problem that combines the well-studied fields of Facility Location and Congestion Games. We call this problem Facility Location for Selfish Commuters and we examine it both from an optimization and a game-theoretic point of view. After examining the existing techniques for solving, facility location, network design, and congestion game problems we provide insights and algorithms for different variants of the general problem. Our contribution in this thesis is manifold. Using counter-examples we show how and why the established techniques of local search and linear programming fail in giving us good approximation algorithms. By examining the structure of the optimal solution, we restrict the search space of optimal solutions. Also, we present a logarithmic approximation algorithm for a variant of the general problem. From a game-theoretic standpoint, we find approximate Nash equilibria and we bound the Price of Anarchy. Finally, by applying sparsification techniques, we propose an approximate solution to a simpler variant of the problem, while at the same time we demonstrate why the use of such techniques fails in the more general setting. (EN)
Προσεγγιστική ισορροπία Νας (EL)
Χωροθέτηση εγκαταστάσεων (EL)
Σχεδίαση δικτύων (EL)
Παίγνια συμφόρησης (EL)
Προσεγγιστικοί αλγόριθμοι (EL)
Facility location (EN)
Network design (EN)
Approximate Nash equilibria (EN)
Approximate algorithms (EN)
Congestion games (EN)
Greek
English
Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών. Εργαστήριο Λογικής και Επιστήμης Υπολογισμών (EL)
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα
http://creativecommons.org/licenses/by-nc-nd/3.0/gr/
National Technical University of Athens
Digital Library of National Technical University of Athens | Dspace@NTUA
Κεντρική Βιβλιοθήκη Ε.Μ.Π.
Ιδρυματικό Αποθετήριο
Διπλωματικές Εργασίες



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)