Τιμολόγηση Καθοδηγούμενη από Δεδομένα για Δρομολόγηση και Έλεγχο Αποδοχής σε Δίκτυα με Χωρητικότητες

Abstract

Στην παρούσα διπλωματική εργασία, εξετάζουμε την απόδοση των prophet inequalities σε Συνδυαστικές Δημοπρασίες όταν οι αξιολογήσεις παρουσιάζουν συμπληρωματικότητες και τα αντικείμενα είναι διαθέσιμα σε πολλά αντίγραφα. Εστιάζουμε στο παραδειγματικό πρόβλημα της άμεσης δρομολόγησης και ελέγχου αποδοχής σε δίκτυα όταν οι ακμές έχουν χωρητικότητα που είναι λογαριθμικά μεγάλη σε σχέση με το πλήθος των ακμών και γνωρίζουμε την κατανομή των αιτημάτων. Η λογαριθμικά μεγάλη χωρητικότητα μας επιτρέπει να λύσουμε προσεγγιστικά την κλασματική χαλάρωση του προβλήματος που μας δίνει πιθανότητες σε μονοπάτια και προσεγγιστικό παράγοντα ίσο με 1 + ε. Υποθέτοντας ότι έχουμε γνώση των συνολικών αιτημάτων που έρχονται σε κάθε ζευγάρι κόμβων, έπειτα χρησιμοποιούμε την έννοια των balanced prices, όπως ορίζονται στο [32] οι οποίες υπολογίζονται με βάση τα μονοπάτια, και αποδομούμε το πρόβλημα σε στιγμιότυπα που πρακτικά συμπεριφέρονται ως ανεξάρτητα και λειτουργούν ως unit-demand.