Αλγόριθμοι Προσέγγισης για τη Δυναμική Εκδοχή του Προβλήματος Min-Sum Set Cover.

Abstract

Στην παρούσα διπλωματική εργασία εξετάζουμε το πρόβλημα δυναμικής κάλυψης συνόλου ελάχιστου αθροίσματος ($\DSSC$) μια φυσιολογική και ενδιαφέρουσα γενίκευση του κλασικού προβλήματος ανανέωσης λίστας. Στο πρόβλημα $\DSSC$ πρέπει να διατηρήσουμε μια ακολουθία μεταθέσεων $(\pi^0, \pi^1, \ldots, \pi^T)$ n τω πλήθος στοιχείων βάσει μιας ακολουθίας συνόλων κάλυψης $\cR = (R^1, \ldots, R^T)$. Στόχος μας είναι να ελαχιστοποιήσουμε το κόστος ανανέωσης απ' την μετάθεση $\pi^{t-1}$ στην $\pi^{t}$, το οποίο ποσοτικοποιείται με την απόσταση Kendall Tau $\dkt(\pi^{t-1}, \pi^t)$, συν το συνολικό κόστος κάλυψης κάθε αιτήματος $R^t$ με την παρούσα μετάθεση $\pi^t$ που είναι στην ουσία η θέση του πρώτου στοιχείου του συνόλου $R^t$ στην μετάθεση $\pi^t$. \\

\noindent Ξεκινάμε με μια ιστορική αναδρομή του προβλήματος παρουσιάζοντας τις διάφορες εκδοχές του προβλήματος που έχουν παρουσιαστεί στην βιβλιογραφία και τους αλγορίθμος που χρησιμοποιούνται για τον σχεδιασμό αλγορίθμων για την κάθε εκδοχή. Η παρουσίαση αυτών των τεχνικών είναι πολύ σημαντική καθώς κτίζουν μια καλή διαίσθηση για το πρόβλημα και επιπλέον βοηθάνε στην κατανόηση των αποτελεσμάτων της offline Dynamic εκδοχής με την οποία και ασχολούμαστε. \\

\noindent Σε επόμενη φάση, συνεχίζουμε με μια ιστορική αναδρομή καθώς και παραλλαγές του προβλήματος. Ξεκινάμε με το πρόβλημα ανανέωσης λίστας(List-Update) και εξηγούμε πως χρησιμοποιώντας την μέθοδο δυναμικού που περιγράψαμε στην προηγούμενη ενότητα μπορούμε να λύσουμε το πρόβλημα με παράγοντα προσέγγισης 2. Επιπλέον, παρουσιάζουμε μια γενικότερη οικογένεια προβλημάτων που εξελίσσονται στον χρόνο και εξηγούμε πως μπορούμε να χρησιμοποιήσουμε Rounding γραμμικών προγραμμάτων προκειμένου να λάβουμε ακριβείς ή και προσεγγιστικές λύσεις για ορισμένα προβλήματα. Χρησιμοποιούμε το πρόβλημα Facility Reallocation on the Real Line για την παρουσίαση αυτής της τεχνικής. \\

\noindent Στην τελευταία ενότητα παρουσιάζουμε τα αποτελέσματά μας για το πρόβλημα $\DSSC$. Ανάγοντας απ' το κλασικό πρόβλημα Κάλυψης Συνόλου(Set Cover), δείχνουμε αρχικά ότι το $\DSSC$ δεν μπορεί να προσεγγιστεί με παράγοντα προσέγγισης $O(1)$ εκτός και αν $\mathrm{P} = \mathrm{NP}$ καθώς και ότι οποιοσδήποτε αλγόριθμος με παράγοντα προσέγγισης $o( \log n)$ (αντίστοιχα $O(r)$) για το $\DSSC$ θα έδινε υπολογαριθμικό παράγοντα προσέγγισης για το Set Cover (ή $ο(r)$ αντίστοιχα αν θεωρήσουμε την εκδοχή όπου κάθε στοιχείο εμφανίζεται το πολύ $r$ φορές στα σύνολα κάλυψης). Η βασική μας συνεισφορά έγκειται στο οτι δείχνουμε πως το πρόβλημα $\DSSC$ μπορεί να προσεγγιστεί σε πολυωνυμικό χρόνο με παράγοντα $O( \log^2 n )$ στην γενική περίπτωση με randomized rounding και με παράγοντα $O(r^2)$, αν όλα τα σύνολα αιτημάτων κάλυψης έχουν πληθικότητα το πολύ $r$, με deterministic rounding.