Conference item icon

Conference item

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, ma...

Expand abstract
Publication status:
Published

Actions


Access Document


Files:
Publisher copy:
10.1007/978-3-030-73879-2_2

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
Host title:
Integer Programming and Combinatorial Optimization. IPCO 2021
Series:
Lecture Notes in Computer Science
Series number:
12707
Pages:
15-29
Place of publication:
Cham, Switzerland
Publication date:
2021-05-05
Event title:
Integer Programming and Combinatorial Optimization 22nd International Conference (IPCO 2021)
Event location:
Atlanta, GA, USA
Event website:
https://sites.gatech.edu/ipco-2021/
Event start date:
2021-05-19
Event end date:
2021-05-21
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
EISBN:
9783030738792
ISBN:
9783030738785
Language:
English
Keywords:
Pubs id:
1308702
Local pid:
pubs:1308702
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