Άμεση χωροθέτηση υπηρεσιών με μετακινούμενες υπηρεσίες

Abstract

Στην παρούσα διπλωματική μελετάμε το πρόβλημα της άμεσης χωροθέτησης υπηρεσιών (online facility location). Η χωροθέτηση υπηρεσιών (facility location) είναι ένα από τα σημαντικότερα προβλήματα στο πεδίο της επιστήμης υπολογιστών και επιχειρησιακής έρευνας με πληθώρα πρακτικών εφαρμογών. Από θεωρητικής πλευράς το πρόβλημα παρέχει εύφορο έδαφος για την ανάπτυξη και εφαρμογή προσεγγιστικών αλγορίθμων και οι αλγόριθμοι για το πρόβλημα αποτελούν από τις σημαντικότερες κατακτήσεις στο πεδίο της θεωρίας προσεγγιστικών αλγορίθμων. Σε πολλές από τις εφαρμογες η είσοδος δεν είναι απόλυτα γνωστή εκ των προτέρων και τα αιτήματα ερχονται σε διακριτές χρονικές στιγμές και ο (άμεσος) αλγόριθμος πρεπει να τα εξυπηρετεί την στιγμή της άφιξης τους. Το πολύ ενδιαφέρον αυτό πρόβλημα εχει μελετηθεί εκτενώς στην βιβλιογραφία η οποία εχει καταλήξει στην πλήρη κατανόηση του απο θεωρητικής σκοπιάς. Μελετάμε το πρόβλημα της άμεσης χωροθέτησης υπηρεσιών και παραθέτουμε μερικά από τα σημαντικότερα αποτελέσματα σε αυτό.

Στην συνέχεια στρέφουμε την προσοχή μας στο πρόβλημα της άμεσης χωροθέτησης υπηρεσιών με μετακινούμενες υπηρεσίες (online facility location with mobile facilities). Μελετάμε τον ήδη γνωστό αλγόριθμο για το πρόβλημα και αποδεικνύουμε οτι είναι ασυμπτωτικά βέλτιστος στην ευθεία των πραγματικών αριθμών. Υποδεικνύουμε ποιό είναι το εμπόδιο στην απόδειξη της βελτιστότητας του αλγορίθμου σε Ευκλείδιους χώρους μεγαλύτερης διαστασης. Στο τελευταιό κεφάλαιο, χρησιμοποιώντας τεχνικές από το κλασικό πρόβλημα της χωροθέτησης υπηρεσιών, δείχνουμε οτι ο αλγόριθμος είναι πράγματι βέλτιστος σε Ευκλείδους χώρους μεγαλύτερης διάστασησ και αναπτύσουμε έναν καινούργιο αλγόριθμο για γενικούς μετρικούς χώρους. Τέλος δείχνουμε ότι ο αλγόριθμος μας είναι ασυμπτωτικά βέλτιστος σε γενικούς μετρικόυς χώρους.