Journal article icon

Journal article

Online k-taxi via Double Coverage and time-reverse primal-dual

Abstract:

We consider the online k-taxi problem, a generalization of the k-server problem, in which k servers are located in a metric space. A sequence of requests is revealed one by one, where each request is a pair of two points, representing the start and destination of a travel request by a passenger. The goal is to serve all requests while minimizing the distance traveled without carrying a passenger. We show that the classic Double Coverage algorithm has competitive ratio 2 k- 1 on HSTs, matching...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1007/s10107-022-01815-6

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
St Anne's College
Role:
Author
ORCID:
0000-0003-3744-0977
Publisher:
Springer
Journal:
Mathematical Programming More from this journal
Volume:
197
Issue:
2
Pages:
499-527
Publication date:
2022-05-13
DOI:
EISSN:
1436-4646
ISSN:
0025-5610
Language:
English
Keywords:
Pubs id:
1308698
Local pid:
pubs:1308698
Deposit date:
2023-03-28

Terms of use


Views and Downloads






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

TO TOP