Online Facility Location with Switching Costs

Postgraduate Thesis uoadl:2244321 331 Read counter

Unit:
Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Library of the School of Science
Deposit date:
2017-11-18
Year:
2017
Author:
Zakynthinou Lydia
Supervisors info:
Δημήτρης Φωτάκης, Επικ. Καθηγητής, ΗΜΜΥ, ΕΜΠ
Ευστάθιος Ζάχος, Καθηγητής, ΗΜΜΥ, ΕΜΠ
Άρης Παγουρτζής, Αναπλ. Καθηγητής, ΗΜΜΥ, ΕΜΠ
Original Title:
Online Facility Location with Switching Costs
Languages:
English
Translated title:
Online Facility Location with Switching Costs
Summary:
Online decision making is a large research area whose literature includes many different aspects and approaches. The problems it studies are based on the following setting. There is a decision-maker who has to make a decision iteratively with no knowledge of the future and receive the cost of their decision in each round. The goal is to perform well over time. Depending on the definition of what consists of a good performance, that is the benchmark to which we compare our algorithm’s total cost, and on the assumptions made, different kinds of problems occur. A particularly interesting benchmark which captures many real life problems where the environment changes over time, is a solution which balances the trade-off between the optimal costs in each round and its stability. Online learning and competitive analysis are two frameworks which study problems in this setting. In this thesis we will discuss the differences between these two frameworks, the efforts to unify them and finally we will demonstrate how such a unifying approach can give a good approximation algorithm for the online facility location problem with switching costs, which falls into this general setting.
Main subject category:
Science
Keywords:
online learning, online convex optimization, facility location, switching costs
Index:
Yes
Number of index pages:
1
Contains images:
No
Number of references:
39
Number of pages:
76
Lydia_Zakynthinou_thesis_MPLA.pdf (479 KB) Open in new window