Online algorithms for dynamic aggregation problems

Abstract

In this PhD thesis, we study online variants of Dynamic Aggregation problems that are generalizations of prominent and well studied online problems. In the online setting, we additionally assume that the input arrives piece-by-piece and that the online algorithm has to provide a solution for the input piece of the current stage before it sees the upcoming input pieces of future stages. The decision quality of the online algorithm is evaluated against an optimal offline algorithm, which is given the whole problem data from the beginning. The performance of the online algorithm is measured by the competitive ratio which is the worst-case ratio between the online cost and the optimal offline cost. We consider the online variants of the Min-Sum Set Cover problem, the K-Facility Reallocation problem and the Dynamic Facility Location problem. For all the aforementioned problems, we design online algorithms and we prove upper bounds on their competitive ratio. Moreover, we construct difficult instances for these problems and we prove lower bounds on the competitive ratio of online algorithms on these instances. The majority the upper bounds are close (or the same) with the lower bounds that we prove and this ensures that our online algorithms are optimal or near optimal.

Σε αυτή την διδακτορική διατριβή, μελετάμε άμεσους αλγόριθμους για προβλήματα Δυναμικής Συνάθροισης. Στην περίπτωση των άμεσων αλγόριθμων θεωρούμε ότι η είσοδοςτων προβλημάτων δεν είναι γνωστή εκ των προτέρων, αλλά αποκαλύπτεται κομμάτι‐κομμάτι στον αλγόριθμο. Τα αποτελέσματα μας αφορούν άμεσες εκδοχές των προβλημάτων Κάλυψης Συνόλου Ελάχιστου Αθροίσματος , Ανακατανομής Κ‐Υπηρεσιών και Δυναμικής Χωροθέτησης Υπηρεσιών. Για όλα αυτά τα προβλήματα σχεδιάζουμε άμεσους αλγόριθμους και αποδεικνύουμε την αποτελεσματικότητά τους. Συγκεκριμένα, αποδεικνύουμε άνω φράγματα στον λόγο ανταγωνιστικότητας των άμεσων αλγορίθμων μας. Ο λόγος ανταγωνιστικότητας ορίζεται ως ο χειρότερος δυνατό λόγος ανάμεσα στο κόστος της λύσης του άμεσου αλγορίθμου και στο κόστος της λύσης ενός βέλτιστου αλγορίθμου, ο οποίος επιπλέον γνωρίζει όλη την είσοδο εκ των προτέρων. Επιπλέον, σχεδιάζουμε δύσκολα στιγμιότυπα για όλα τα προβλήματα που μελετάμε, τα οποία μας δίνουν την δυνατότητα να αποδείξουμε κάτω φράγματα στον καλύτερο δυνατό λόγο ανταγωνιστικότητας που μπορεί να επιτύχει οποιοσδήποτε άμεσος αλγόριθμος. Αυτό σημαίνει ότι κανένας αλγόριθμος δεν μπορεί να πετύχει καλύτερο λόγο ανταγωνιστικότητας από το κάτω φράγμα που ισχύει για τα δύσκολα στιγμιότυπα. Στις περισσότερες περιπτώσεις, τα κάτω φράγματα είναι πολύ κοντά στα άνω φράγματα (σε κάποιες περιπτώσεις ταυτίζονται) και το γεγονός αυτό αποδεικνύει ότι οι αλγόριθμοι που έχουμε διατυπώσει και αναλύσει είναι βέλτιστοι ή σχεδόν βέλτιστοι για το αντίστοιχο πρόβλημα.