mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Defenses » November 2017 » Isidoros Tziotis
download defense details: { pdf }

MSc thesis defense presentation

Isidoros Tziotis defends his MSc thesis

Date: Wednesday, 22 Nov 2017
Time: 17:00
Location: School of Electrical and Computer Engineering (old buildings), 1.1.31
Thesis title: On-line Shortest Path with Switching Cost
Committee:

Thesis abstract

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.

Reporter

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