Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://opus.kobv.de/zib/volltexte/2005/889/

Hiller, Benjamin

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

pdf-Format:
Dokument 1.pdf (245 KB)
ps-Format:
Dokument 1.ps (369 KB)

Kurzfassung in Englisch

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\|)$.

Freie Schlagwörter (englisch): probabilistic competitive analysis , Dial-a-Ride problem , online algorithms , IGNORE strategy
MSC - Klassifikation 68Q25
MSC - Klassifikation 68W25
CCS - Klassifikation F.2.2
Abteilung: ZIB Allgemein
DDC-Sachgruppe: Allgemeines, Wissenschaft
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 05-56
Quelle: no further publication planned / keine weitere Veröffentlichung vorgesehen
Sprache: Englisch
Erstellungsjahr: 2005
Publikationsdatum: 09.12.2005
Bemerkung: printed version not available / keine gedruckte Version verfügbar

Metadatensuche | Volltextsuche | Browsen | Die neuesten Publikationen | Veröffentlichen
Fragen und Anregungen an bibliothek@zib.de
Letzte Änderung: