Alternative settings and models of the certain news network problem
Loading...
Date
2020-02
Authors
Naib, Sameer
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The classic k-server problem has been studied extensively in the context of competitive analysis for online problems. In this problem, a set of k servers move on a metric space to serve requests that appear in an online fashion on the nodes of the space. The goal is to move servers in a way to minimize the total distance moved by all of them.
The Certain News Network (CNN) problem is a variant of the k-server problem where there is only one server `serving' requests on a grid metric space. To serve a request, the server should be vertically or horizontally aligned (not necessarily co-located) with the request. The orthogonal CNN problem is a restricted setting of the CNN problem in which every new request is aligned with the previous request. The best existing lower and upper bounds for the competitive ratios in the orthogonal setting are respectively 3 and 6.464. In this thesis, we tighten the gap between upper and lower bounds for the orthogonal CNN problem by providing better algorithms that achieves a competitive ratio of at most 5. Our algorithm, named Walk-and-Jump (WJ) algorithm, is based on the concept of work function that is studied before for both k-server and CNN problems.
We use the concept of work function in designing the Walk-and-Jump algorithm. Moreover, in the worst-case sequences that we studied, the WJ algorithm has a cost that is no more than three times the cost of an optimal offline algorithm. Given this observation, we conjecture that the analysis can be improved to show the WJ algorithm is indeed optimal and has a competitive ratio of 3.
Besides this main result, we also consider the advice model for the orthogonal CNN problem. Under this model, the online algorithm receives certain ``advice" about the input sequence that is generated by a benevolent offline oracle. We show that advice of size theta(n) is sufficient and necessary to achieve an optimal solution for the orthogonal CNN problem.
Description
Keywords
Online Algorithms, Potential Function, Advice, Competitive Ratio, CNN Problem, Work Fucntion, Greedy Algorithm