1. Home page
  2. Search

Online Shortest Path with Switching Cost

This item is provided by the institution :
/aggregator-openarchives/portal/institutions/uoa   

Repository :
Pergamos Digital Library   

see the original item page
in the repository's web site and access all digital files if the item*



Online Shortest Path with Switching Cost
Τζιώτης Ισίδωρος (EL)
Tziotis Isidoros (EN)
born_digital_postgraduate_thesis
Διπλωματική Εργασία (EL)
Postgraduate Thesis (EN)
2017
Ένα χαρακτηριστικό 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. (EL)
A typical on-line problem proceeds in rounds, where in each round an on-line algorithm is given a request and needs to serve it. We will focus on a specific class of on-line problems known as Smooth On-line Convex Optimization (SOCO) problems. Two mature research fields that study such problems are competitive analysis and on-line learning. We will dive into their interrelationship and we will explain how we can benefit by introducing regularization, a standard technique from on-line learning in the framework of competitive analysis. Subsequently, we will turn our attention towards a rounding technique introduced over the last couple of years, called exponential clocks. Finally, we will define a new problem in the class SOCO, namely On-line Shortest Path with Switching Cost. Using the toolbox provided by the literature we will obtain an on-line fractional solution sacrificing a logarithmic factor. We will wrap up presenting a new on-line rounding algorithm using exponential clocks which will derive a O(logmlog n)-approximation for the On-line Shortest Path with Switching Cost problem. (EN)
Θετικές Επιστήμες
Θετικές Επιστήμες (EL)
Science (EN)
English
Σχολή Θετικών Επιστημών » Τμήμα Μαθηματικών » Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και Υπολογισμού » Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Βιβλιοθήκη και Κέντρο Πληροφόρησης » Βιβλιοθήκη Σχολής Θετικών Επιστημών
https://creativecommons.org/licenses/by-nc/4.0/
University of Athens
Pergamos Digital Library
Postgraduate Thesis



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)