Online Shortest Path with Switching Cost

Postgraduate Thesis uoadl:2285490 271 Read counter

Unit:
Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Library of the School of Science
Deposit date:
2017-11-23
Year:
2017
Author:
Tziotis Isidoros
Supervisors info:
Δημήτρης Φωτάκης, Αναπληρωτής Καθηγητής, Τμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Ηλ.Υπολογιστών, ΕΜΠ
Original Title:
Online Shortest Path with Switching Cost
Languages:
English
Translated title:
Online Shortest Path with Switching Cost
Summary:
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.
Main subject category:
Science
Keywords:
Online Convex Optimization, Smooth Optimization, Online Learning, Shortest Paths, Exponential Clocks
Index:
No
Number of index pages:
0
Contains images:
No
Number of references:
32
Number of pages:
54
Isidoros_Tziotis_Final.pdf (1 MB) Open in new window