889
eng
reportzib
0
2005-12-09
2005-12-09
--
Probabilistic Competitive Analysis of a Dial-a-Ride Problem on Trees Under High Load
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\|)$.
05-56
889
urn:nbn:de:0297-zib-8896
Benjamin Hiller
ZIB-Report
05-56
eng
uncontrolled
probabilistic competitive analysis
eng
uncontrolled
Dial-a-Ride problem
eng
uncontrolled
online algorithms
eng
uncontrolled
IGNORE strategy
Informatik, Informationswissenschaft, allgemeine Werke
Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3)
Analysis of algorithms and problem complexity [See also 68W40]
Approximation algorithms
ZIB Allgemein
Hiller, Benjamin
ONLINE-PLANNING
https://opus4.kobv.de/opus4-zib/files/889/ZR-05-56.pdf
https://opus4.kobv.de/opus4-zib/files/889/ZR-05-56.ps