mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Isidoros Tziotis Anonymously browsing from 34.204.52.4 at 15:27:30, 24-03-2019. login

MSc thesis of Isidoros Tziotis

On-line Shortest Path with Switching Cost

Supervisor: Dimitris Fotakis

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.

Download

This MSc thesis is not available for download.

Reporter

Page updates

No recent updates.

Feeds RSS and Atom feeds

posts
all posts RSS
news RSS
announcements RSS
website news RSS
events
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2019 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.