Techniques For Design And Analysis Of Algorithms For Problems In Metric Spaces

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.