Άμεσοι Αλγόριθμοι Επαυξημένοι με Προβλέψεις για Προβλήματα Χωροθέτησης και Ανάθεσης Πόρων

Abstract

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