ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Probabilistic Competitive Analysis of a Dial-a-Ride Problem on Trees Under High Load (2005)

Hiller, Benjamin

add to mindlist on the mindlist

Details

Publication Date: 2020-03-09

Description: In this paper we consider a simple variant of the Online Dial-a-Ride Problem from a probabilistic point of view. To this end, we look at a probabilistic version of this online Dial-a-Ride problem and introduce a probabilistic notion of the competitive ratio which states that an algorithm performs well on the vast majority of the instances. Our main result is that under the assumption of high load a certain online algorithm is probabilistically $(1+o(1))$-competitive if the underlying graph is a tree. This result can be extended to general graphs by using well-known approximation techniques at the expense of a distortion factor~$O(\log\|V\|)$.

Keywords: ddc:000

Language: English

Type: reportzib , doc-type:preprint

Format: application/pdf

Format: application/postscript

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

OPUS

PDF

Overview

hit 1 - 1 | 1 hit