Μονάδα:
Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2017-11-23
Συγγραφέας:
Τζιώτης Ισίδωρος
Στοιχεία επιβλεπόντων καθηγητών:
Δημήτρης Φωτάκης, Αναπληρωτής Καθηγητής, Τμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Ηλ.Υπολογιστών, ΕΜΠ
Πρωτότυπος Τίτλος:
Online Shortest Path with Switching Cost
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Online Συντομότερα Μονοπάτια με Κόστος Εναλλαγής
Περίληψη:
Ένα χαρακτηριστικό on-line πρόβλημα διεξάγεται σε γύρους, όπου σε κάθε γύρο ένας on-line αλγόριθμος δέχεται ένα αίτημα και οφείλει να το ικανοποιήσει. Θα επικεντρωθούμε σε μία συγκεκριμένη οικογένεια on-line προβλημάτων γνωστά ως Smooth On-line Convex Optimization (SOCO) προβήματα. Δύο γνωστά επιστημονικά πεδία που μελετούν τέτοια προβλήματα είναι το πεδίο competitive analysis και το πεδίο on-line learning. Θα εμβαθύνουμε στη σχέση των δύο πεδίων και θα εξηγήσουμε πως μπορούμε να επωφεληθούμε εισάγωντας την τεχνική regularization από το πεδίο του on-line learning στο competitive analysis. Στη συνέχεια θα εστιάσουμε σε μία τεχνική
rounding η οποία εμφανίστηκε στη βιβλιογραφία τα τελευταία χρόνια και ονομάζεται exponential clocks. Τέλος, θα ορίσουμε ένα νέο πρόβλημα της οικογένειας SOCO, το On-line Shortest Paths with Switching Cost. Χρησιμοποιώντας εργαλεία από τη βιβλιογραφία θα πάρουμε μία on-line fractional λύση του προβλήματος θυσιάζοντας ένα λογαριθμικό παράγοντα. Θα ολοκληρώσουμε παρουσιάζοντας ένα νέο rounding αλγόριθμο χρησιμοποιώντας exponential clocks, ο οποίος θα επιτύχει μια O(logmlog n)- προσέγγιστική λύση για το πρόβλημα On-line Shortest Path with Switching Cost.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
Online κυρτή βελτιστοποίηση, ομαλή βελτιστοποίηση, On-line Learning, Συντομότερα Μονοπάτια, Εκθετικά Ρολόγια
Αρ. σελίδων ευρετηρίου:
0
Αρ. βιβλιογραφικών αναφορών:
32
