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.