Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/16479
Title: Techniques For Design And Analysis Of Algorithms For Problems In Metric Spaces
Authors: Νάκος Βασίλειος
Φωτάκης Δημήτριος
Keywords: algorithms
online
k-server
mobile facility location
incremental clustering
fractional
randomized
Issue Date: 12-Nov-2012
Abstract: We study problems where we have access to the input piece-by-piece in a serial fash-ion, i.e., in the order that the input is fed to the algorithm, without having the entire inputavailable from the start. We focus to metric spaces problems, where the triangle inequal-ity holds. We take a glimpse at the k-server problem and present some classical, as wellas some new results for it. The k-server problem is the most fundamental problem in thefield of online algorithms, and has been studied for decades. The previous year, the work ofBansal et al. was breakthrough as it proposed the first (randomized) polylogarithmic algo-rithm in decades. Moreover, we also present the design and analysis of efficient fractionalalgorithms for online problems as mentioned before, based on two techniques: the one ispuerly combinatorial ,whereas the second one is based on a primal-dual approach and a solu-tion of a system of differential equations to establish the competitive ratio. Last but not least,we study incremental sum-radii clustering and an extension of mobile facility location to anonline setting, and present some results about the structures of the problems, algorithms forthe general case and more competitive algorithms for some specialised,but not trivial, cases.
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/16479
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File SizeFormat 
DT2012-0271.pdf365.28 kBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.