Competitive analysis of k-server variants and metrical task systems

Coester, C

Abstract:: In the online k-server problem, an algorithm controls k mobile servers in a metric space. One by one, requests arrive at points of the space, and the algorithm must serve each request by selecting a server to visit it. The goal is to minimize the total distance traveled by all servers. In the framework of competitive analysis, we study two variants of the k-server problem, the infinite server problem and the k-taxi problem, and the more general metrical task systems problem.

The infinite server problem is the variant of the k-server problem where the number of servers is infinite, initially all starting at the same point. We obtain a surprisingly tight connection between the infinite server problem and the resource augmentation version of the k-server problem. Using this connection, we also improve the known lower bounds for the resource augmented k-server problem.

The k-taxi problem generalizes the k-server problem in that a request consists not of one point, but two points s and t, representing the start and destination of a taxi request. To serve such a request, a server (taxi) must move first to s and then to t. This problem becomes particularly difficult when the cost is defined as the distance of empty runs only. Indeed, we show an exponential gap between the competitive ratio of the k-taxi problem and that of the k-server problem. A main positive result is an O(2^k log n)-competitive algorithm for arbitrary n-point metrics.

Metrical task systems are a general framework subsuming many other online problems, including the k-server problem. Here, the algorithm suffers two kinds of costs, movement and service costs. For HST metrics, using an entropy regularization approach, we obtain tight bounds on the refined guarantees, i.e., movement and service costs are simultaneously optimally competitive against the optimal total cost. This also improves the refined guarantees for general metrics.

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Cite

Cite this record

APA Style

Coester, C. (2019). Competitive analysis of k-server variants and metrical task systems [PhD thesis]. University of Oxford.

MLA Style

Coester, C. Competitive Analysis of k-Server Variants and Metrical Task Systems. University of Oxford, 2019.

Chicago Style

Coester, C. 2019. “Competitive Analysis of k-Server Variants and Metrical Task Systems.” PhD thesis, University of Oxford.
Share
Print

Access Document

Files:: final.pdf

(Preview, Dissemination version, pdf, 853.4KB, Terms of use)

Authors

+ Coester, C More by this author

Division:: MPLS
Department:: Computer Science
Role:: Author

Contributors

+ Koutsoupias, E

Department:: University of Oxford
Role:: Supervisor

+ Kanade, V

Department:: University of Oxford
Role:: Examiner

+ Gupta, A

Department:: CMU
Role:: Examiner

+ Engineering & Physical Sciences Research Council More from this funder

Grant:: 1652110

DOI:: 10.5287/ora-eyb5myrxo
Type of award:: DPhil
Level of award:: Doctoral
Awarding institution:: University of Oxford

Language:: English
Keywords:: Online algorithms, k-server
UUID:: uuid:4d6d86fb-564f-4a34-be8d-e0ba6701f7d3
Deposit date:: 2020-03-02

Related item:: The Online k-Taxi Problem
Description:: We consider the online k-taxi problem, a generalization of the k-server problem, in which k taxis serve a sequence of requests in a metric space. A request consists of two points s and t, representing a passenger that wants to be carried by a taxi from s to t. The goal is to serve all requests while minimizing the total distance traveled by all taxis. The problem comes in two flavors, called the easy and the hard k-taxi problem: In the easy k-taxi problem, the cost is defined as the total distance traveled by the taxis; in the hard k-taxi problem, the cost is only the distance of empty runs.The hard k-taxi problem is substantially more difficult than the easy version with at least an exponential deterministic competitive ratio, Omega(2^k), admitting a reduction from the layered graph traversal problem. In contrast, the easy k-taxi problem has exactly the same competitive ratio as the k-server problem. We focus mainly on the hard version. For hierarchically separated trees (HSTs), we present a memoryless randomized algorithm with competitive ratio 2^k-1 against adaptive online adversaries and provide two matching lower bounds: for arbitrary algorithms against adaptive adversaries and for memoryless algorithms against oblivious adversaries. Due to well-known HST embedding techniques, the algorithm implies a randomized O(2^k log n)-competitive algorithm for arbitrary n-point metrics. This is the first competitive algorithm for the hard k-taxi problem for general finite metric spaces and general k. For the special case of k=2, we obtain a precise answer of 9 for the competitive ratio in general metrics. With an algorithm based on growing, shrinking and shifting regions, we show that one can achieve a constant competitive ratio also for the hard 3-taxi problem on the line (abstracting the scheduling of three elevators).
Related item:: The infinite server problem
Description:: We study a variant of the k-server problem, the infinite server problem, in which infinitely many servers reside initially at a particular point of the metric space and serve a sequence of requests. In the framework of competitive analysis, we show a surprisingly tight connection between this problem and the (h,k)-server problem, in which an online algorithm with k servers competes against an offline algorithm with h servers. Specifically, we show that the infinite server problem has bounded competitive ratio if and only if the (h,k)-server problem has bounded competitive ratio for some k=O(h). We give a lower bound of 3.146 for the competitive ratio of the infinite server problem, which implies the same lower bound for the (h,k)-server problem even when k/h goes to infinity and holds also for the line metric; the previous known bounds were 2.4 for general metric spaces and 2 for the line. For weighted trees and layered graphs we obtain upper bounds, although they depend on the depth. Of particular interest is the infinite server problem on the line, which we show to be equivalent to the seemingly easier case in which all requests are in a fixed bounded interval away from the original position of the servers. This is a special case of a more general reduction from arbitrary metric spaces to bounded subspaces. Unfortunately, classical approaches (double coverage and generalizations, work function algorithm, balancing algorithms) fail even for this special case.
Related item:: Pure entropic regularization for metrical task systems
Description:: We show that on every n-point HST metric, there is a randomized online algorithm for metrical task systems (MTS) that is 1-competitive for service costs and O(log n)-competitive for movement costs. In general, these refined guarantees are optimal up to the implicit constant. While an O(log n)-competitive algorithm for MTS on HST metrics was developed by Bubeck et al (SODA 2019), that approach could only establish an O((log n)^2)-competitive ratio when the service costs are required to be O(1)-competitive. Our algorithm is an instantiation of online mirror descent with the regularizer derived from a multiscale conditional entropy.In fact, our algorithm satisfies a set of even more refined guarantees; we are able to exploit this property to combine it with known random embedding theorems and obtain, for any n-point metric space, a randomized algorithm that is 1-competitive for service costs and O((log n)^2)-competitivefor movement costs.

Terms of use

Copyright holder:: Coester, C

Licence:: Terms and Conditions of Use for Oxford University Research Archive

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

Thesis

Competitive analysis of k-server variants and metrical task systems

Actions

Access Document

Authors

Contributors

Terms of use

Views and Downloads

Altmetrics

Dimensions

Thesis

Competitive analysis of k-server variants and metrical task systems

Actions

Access Document

Authors

Contributors

Funding

Bibliographic Details

Item Description

Related Items

Terms of use

Metrics

Views and Downloads

Altmetrics

Dimensions