Postgraduate Thesis uoadl:2285490 271 Read counter

Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού

Library of the School of Science

Library of the School of Science

2017-11-23

2017

Tziotis Isidoros

Δημήτρης Φωτάκης, Αναπληρωτής Καθηγητής, Τμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Ηλ.Υπολογιστών, ΕΜΠ

Online Shortest Path with Switching Cost

English

Online Shortest Path with Switching Cost

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

Science

Online Convex Optimization, Smooth Optimization, Online Learning, Shortest Paths, Exponential Clocks

No

0

No

32

54