Χρονομεταβαλλόμενη Βελτιστοποίηση Σε Μητροειδή

Abstract

Το πρόβλημα της Χρονομεταβαλλόμενης Βελτιστοποίησης σε Μητροειδή είναι μια γενίκευση του κλασικού προβλήματος εύρεσης βάσης ελαχίστου κόστους. Προτάθηκε από τους Gupta, Talwar και Wieder προκειμένου να μοντελοποιηθούν συστήματα τα οποία πρέπει να διατηρούνται συνεχώς, ενώ τα κόστη μεταβάλλονται με την πάροδο του χρόνου. Καθώς ο χρόνος περνάει, το κόστος των στοιχείων μπορεί να αλλάζει και αυτό οδηγεί σε ένα συμβιβασμό μεταξύ της διατήρησης μιας βάσης χαμηλού κόστους και της "σταθερότητας" της λύσης. Πιο συγκεκριμένα, η είσοδος είναι μια ακολουθία συναρτήσεων κόστους (μία για κάθε χρονική στιγμή). Ενώ αλλάζουμε τη βάση από βήμα σε βήμα, επιβάλλουμε ένα επιπλέον ενιαίο κόστος απόκτησης για κάθε τέτοια αλλαγή.Στην παρούσα διπλωματική εργασία παρουσιάζουμε τον πρώτο ντετερμινιστικό rounding αλγόριθμο, που πετυχαίνει O(logr)-προσέγγιση για το πρόβλημα, όπου r είναι ο βαθμός του Μητροειδούς, και που εγγυάται σταθερή προσέγγιση στο κόστος κράτησης. Οι Gupta et al. είχαν παρουσιάσει έναν τυχαιοκρατικό rounding αλγόριθμο που επίσης πετυχαίνει προσέγγιση O(logr), αλλά αυτό ισχύει τόσο για το κόστος κράτησης όσο και για το κόστος απόκτησης. Ο αλγόριθμος μας βασίζεται στην καλά κατανοητή δομή του πολυτόπου των ανεξαρτήτων συνόλων και εισάγει μια νέα rounding τεχνική που ενδέχεται να είναι ανεξαρτήτου ενδιαφέροντος. Επιπλέον, παρέχουμε τις πρώτες αποδείξεις για integrality γραμμικών προγραμμάτων για προβλήματα Χρονομεταβαλλόμενης Συνδυαστικής Βελτιστοποίησης. Συγκεκριμένα, δείχνουμε ότι το ΓΠ για τη Χρονομεταβαλλόμενη Βελτιστοποίηση σε Μητροειδή Διαμέρισης είναι ακέραιο. Δείχνουμε, επίσης, οτι το ΓΠ για τη Χρονομεταβαλλόμενη Βελτιστοποίηση σε Μητροειδή, για δύο χρονικές στιγμές, ακόμα και αν τα δύο Μητροειδή είναι διαφορετικά, είναι ακέραιο.