Back to search

National and Kapodistrian University of Athens

Online Shortest Path with Switching Cost

Abstract

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.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Τζιώτης Ισίδωρος
  • Tziotis Isidoros

Subjects

dc:subject × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:2285490

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Τζιώτης Ισίδωρος; Tziotis Isidoros. Online Shortest Path with Switching Cost. 2017. https://pergamos.lib.uoa.gr/uoa/dl/object/2285490