{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:2285490"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:2285490","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Online Shortest Path with Switching Cost","abstract":"Ένα χαρακτηριστικό 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.","abstract_html":"Ένα χαρακτηριστικό 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.","abstract_has_math":false,"creators":["Τζιώτης Ισίδωρος","Tziotis Isidoros"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017","date_published":"2017","updated_at":"2026-11-19T05:30:07Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2285490"],"render_values":[{"text":"uoadl:2285490","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2285490","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2285490","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A2285490","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Τζιώτης Ισίδωρος","Tziotis Isidoros"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2285490","https://pergamos.lib.uoa.gr/uoa/dl/object/2285490"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ένα χαρακτηριστικό 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.","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."]},{"key":"dc:title","label":"Title","values":["Online Shortest Path with Switching Cost"]}]}],"canonical_facts":{"dc:creator":["Τζιώτης Ισίδωρος","Tziotis Isidoros"],"dc:date":["2017"],"dc:description":["Ένα χαρακτηριστικό 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.","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."],"dc:identifier":["uoadl:2285490","https://pergamos.lib.uoa.gr/uoa/dl/object/2285490"],"dc:language":["English"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Online Shortest Path with Switching Cost"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:30:07Z"}