Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Ισίδωρος Τζιώτης

MSc thesis of Ισίδωρου Τζιώτη

On-line Shortest Path with Switching Cost

Supervisor: Δημήτρης Φωτάκης

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 Optimiza- tion (SOCO) problems. Two mature research fields that study such problems are competitive analysis and on-line learning. We will dive into their interrela- tionship and we will explain how we can benefit by introducing regularization, a standard technique from on-line learning in the framework of competitive anal- ysis. 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 pre- senting a new on-line rounding algorithm using exponential clocks which will derive a log m log n-approximation for the On-line Shortest Path with Switching Cost problem.

Work in progress.


This MSc thesis is not available for download.


Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.