Approximation Algorithms for Online Facility Location and Radii Facility Location

Abstract

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