Conference item icon

Conference item

The online π‘˜-taxi problem

Abstract:

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 dis...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1145/3313276.3316370

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Engineering and Physical Sciences Research Council More from this funder
Publisher:
Association for Computing Machinery Publisher's website
Pages:
1136-1147
Publication date:
2019-06-23
Acceptance date:
2019-02-08
DOI:
Pubs id:
pubs:991872
URN:
uri:9f63c7bc-4cfb-4208-84da-d760b3be0195
UUID:
uuid:9f63c7bc-4cfb-4208-84da-d760b3be0195
Local pid:
pubs:991872
ISBN:
978-1-4503-6705-9

Terms of use


Metrics



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

TO TOP