Μοντέλα Τυχαίας Διάταξης και Προφήτη για Άμεσα Επαυξήσιμα Ακέραια Προγράμματα

Abstract

Στην παρούσα διπλωματική μελετάμε προβλήματα της οικογένειας των Άμεσων Επαυξήσιμων Ακέραιων Προγραμμάτων (Online Augmentable Integer Programmes, AIPs) στα μοντέλα Τυχαίας Διάταξης και Προφήτη. Τα δύο αυτά μοντέλα είναι λιγότερο απαισιόδοξα από την κλασσική ανάλυση χειρότερης περίπτωσης, παραμένοντας πάρα τάυτα ιδιαίτερα ελκυστικά από θεωρητικής σκοπιάς, με αποτέλεσμα πλήθος προβλημάτων να έχει αναλυθεί υπό το πρίσμα τους. Ξεκινάμε εξετάζοντας διάφορα σημαντικά προβλήματα που έχουν μελετηθεί σε καθένα από τα δύο μοντέλα, δίνοντας ιδιαίτερη έμφαση στα θεμελιώδη Secretary Problem (στο μοντέλο Τυχαίας Διάταξης) και Prophet Inequality Problem (στο οποίο οφείλει το όνομά του το μοντέλο Προφήτη), καθώς και στις επεκτάσεις τους. Για κάθε πρόβλημα που εξετάζουμε, παρουσιάζουμε και αναλύουμε γνωστούς, απλούς αλγορίθμους που παρ’ όλα αυτά είναι βέλτιστοι σε κάποιες περιπτώσεις και σχεδόν βέλτιστοι στις υπόλοιπες. Επίσης αναφέρουμε τα τρέχοντα καλύτερα άνω και κάτω φράγματα για κάθε πρόβλημα.

Έπειτα, εστιάζουμε στην κλάση των AIPs, η οποία περιλαμβάνει διάφορα ενδιαφέροντα προβλήματα, μεταξύ των οποίων τα Άμεσο Κάλυμμα Συνόλων (Online Set Cover), Άμεσα Ακέραια Προγράμματα Κάλυψης (Online Covering Integer Programmes), Άμεση Μετρική και Μη-Μετρική Χωροθέτηση Υπηρεσιών (Online Metric and Non-Metric Facility Location) και Άμεσο Δέντρο Steiner (Online Steiner Tree). Σε όλα αυτά τα προβλήματα πλην του τελευταίου, πρόσφατα αποτελέσματα έχουν οδηγήσει σε αλγορίθμους για το μοντέλο Τυχαίας Διάταξης, των οποίων οι λόγοι ανταγωνιστικότητας είναι σημαντικά βελτιωμένοι συγκριτικά με τους καλύτερους εφικτούς στο πλήρως ανταγωνιστικό μοντέλο. Επιπλέον, μία πρόσφατα αποδεδειγμένη αναγωγή δείχνει πως η ύπαρξη ενός ανταγωνιστικού αλγορίθμου για ένα AIP στο μοντέλο Τυχαίας Διάταξης συνεπάγεται την ύπαρξη ενός ανταγωνιστικού αλγορίθμου στο μοντέλο Προφήτη. Παρουσιάζουμε τους αλγορίθμους και τα αποτελέσματα αυτά λεπτομερώς, εξετάζοντας σε βάθος τη θεωρητική ανάλυσή τους και τη διαίσθηση στην οποία βασίζονται. Τέλος, κάνουμε ιδιαίτερη αναφορά στο Άμεσο Δέντρο Steiner, για το οποίο είναι γνωστό ότι, παρότι είναι εύκολο να αντιμετωπιστεί στο μοντέλο Προφήτη, εντούτοις στο μοντέλο Τυχαίας Διάταξης δεν είναι ευκολότερο από ότι στο πλήρως ανταγωνιστικό μοντέλο.