Αλγόριθμοι για το πρόβλημα του Ελαχίστου Συνδετικού Δέντρου σε Χρονικά Μεταβαλλόμενα Στιγμιότυπα

Abstract

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

Για τα προβλήματα αυτά, εκτός από την offline υπάρχει και η online εκδοχή όπου η ανεξάρτητη συνάρτηση κόστους κάθε χρονικής στιγμής δεν είναι γνωστή πριν από τη στιγμή αυτή. ΄Ενα από τα πρώτα προβλήματα αυτού του είδους που μελετήθηκε είναι το Multistage Matroid Maintenance, όπου κάθε χρονική στιγμή πρέπει να επιλέγεται ένα σύνολο στοιχείων, ώστε να διατηρείται μία βάση του μητροειδούς, και με το κόστος να προκύπτει από τα στιγμιαία κόστη των στοιχείων και από το πλήθος των αλλαγών επιλογής ανά στοιχείο. Οι (Gupta, Talwar, Wieder, ICALP 2014) έδωσαν διαφόρους λογαριθμικούς προσεγγιστικούς αλγορίθμους για το πρόβλημα αυτό, ενώ εξέτασαν ειδικές περιπτώσεις μητροειδών και την online εκδοχή του προβλήματος.

Στη διπλωματική αυτή εργασία μελετάται το Multistage Matroid Maintenance στην ειδική περίπτωση που το μητροειδές είναι γραφικό και το κόστος επιλογής νέου στοιχείου (ακμής) είναι κοινό για κάθε στοιχείο και χρονική στιγμή, με στόχο τη βελτίωση των λόγων προσέγγισης. Δείχνεται ότι το άμεσο ανάλογο της dual fitting απόδειξης των (Gupta, Talwar, Wieder, ICALP 2014) δεν μπορεί να χρησιμοποιηθεί για την απόδειξη καλύτερου λόγου προσέγγισης από τον υπάρχοντα λογαριθμικό. Παρουσιάζεται ένας άπληστος αλγόριθμος και αποδεικνύεται ότι υπολογίζει βέλτιστη λύση σε διάφορες οικογένειες στιγμιοτύπων, συγκεκριμένα σε στιγμιότυπα με γράφημα όπου κάθε ακμή ανήκει σε έναν το πολύ κύκλο και σε στιγμιότυπα με μέχρι και τρεις χρονικές στιγμές. Ακόμη, αποδεικνύεται ένα σύνολο συνδυαστικών ιδιοτήτων οι οποίες έχουν ανεξάρτητο ενδιαφέρον και ενδέχεται να είναι χρήσιμες για την περαιτέρω ενασχόληση με το πρόβλημα αυτό. Τέλος, παρουσιάζεται ένα σύνολο παραμετρικών αλγορίθμων για τον υπολογισμό της βέλτιστης λύσης καθώς και των ορίων κόστους των λύσεων του απλήστου αλγορίθμου για δεδομένα στιγμιότυπα, οι οποίοι μάλιστα έχουν υλοποιηθεί και αξιολογηθεί πειραματικά.