Models and Algorithms for Online Server Routing

Combinatorial optimization is the discipline that studies problems in which one seeks to minimize or maximize an objective function by appropriately choosing the values of some variables from within an allowed finite set. In a typical combinatorial optimization problem, the feasibility of a solution can be efficiently verified, but the number of feasible solutions is so large that an exhaustive search of an optimal solution is doomed to failure. Thus, efficient combinatorial optimization algorithms need to exploit the structure of the problem being solved. While the classical approach to a combinatorial optimization problem is to assume that all relevant data are available before a solution method is applied, it has recently become more and more evident that in many applications data arrive step by step and a partial solution needs to be maintained at every step. Typical examples of online problems are the scheduling of processes in an operating system, or the trade of stocks in a financial market. In these applications the data is arriving over time and the algorithm that solves the problem has to be online, meaning that it has to keep at every time a solution that has been produced without knowledge of future data. It is quite clear that, because of this lack of information about the future, an online algorithm will not in general be able to produce the optimal solution. Competitive analysis is a theoretical framework that allows to quantify the worst-case suboptimality of the solutions found by an online algorithm. An online algorithm is called competitive if it produces solutions whose cost is always within a constant factor of the optimal solution. In this thesis we study competitive algorithms for server routing problems. In a server routing problem, one or more servers move in a metric space in order to visit some requested points in the space. The objective is to minimize some function of the movement of the servers. An important example is the traveling salesman problem, in which a salesman has to find a round-trip tour through a set of cities in order to minimize the total length of the tour. We consider online versions of this and other server routing problem, in which the points to be visited are released over time. After giving a brief introduction to the field of online optimization in the first chapter of this thesis, in Chapter 2 we review the basic complexity results for offline server routing problems, we introduce formally the online server routing frame- work and we survey the state of the art. We show the basic proof techniques and we discuss several attempts in the literature to extend the basic competitive analysis setting. In Chapter 3, we consider the online asymmetric traveling salesman problem from the point of view of competitive analysis. For the homing version, where the server has to return to its starting point, we give an algorithm that has the best possible competitive ratio. We also consider the nomadic version (where returning to the starting point is not mandatory) and prove that it does not admit constant competitive algorithms. However, for the nomadic version we prove a competitive ratio as a function of the amount of asymmetry of the space. We also consider the competitiveness of zealous algorithms, in which, intuitively, the server is not allowed to remain idle when there are outstanding requests. Finally we discuss the issue of polynomial time online algorithms for the problem. In Chapter 4, we study the online prize-collecting traveling salesman problem. After discussing the approximation ratio of the offline version, we give a 7/3-competitive algorithm. We also consider the special case of the halfline as the metric space, for which we prove lower and upper bounds of 1.89 and 2, respectively, on the competitive ratio of deterministic algorithms. In Chapter 5, we consider the online nomadic traveling salesman and the online traveling repairman with k servers. We give competitive algorithms whose competitive ratios match the ones for the single server variants. For the special case of the real line, we prove the existence of algorithms with competitive ratio 1 + O((log k)/k), meaning that we can approach the optimal cost as k grows. We also show that this phenomenon is limited to the one dimensional case, since already in the Euclidean plane, we prove a lower bound of 4/3 for the online nomadic TSP and of 5/4 for the online TRP independently of the number of servers. Finally, we give resource augmentation results that are asymptotically best possible as the number of online servers grows beyond the number of offline servers. In Chapter 6, in order to address the limits of competitive analysis, we introduce a new model for online server routing based on adversarial queueing theory. The model addresses the stability of online algorithms that are continuously operating. We call an online algorithm stable if there exists an upper bound on the number of unserved requests at any time that does not depend on the time the system has been running. We consider a number of natural algorithms in this model and we prove the existence of algorithms that are stable and such that the maximum flow time of a request also does not depend on the time the system has been running