mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Defenses » November 2017 » Isidoros Tziotis Anonymously browsing from 54.92.201.232 at 10:29:43, 15-12-2017. login
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

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 – 2017 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.