Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

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

Harks, Tobias ; Heinz, Stefan ; Pfetsch, Marc E. ; Vredeveld, Tjark

Online Multicommodity Routing with Time Windows

pdf-Format:
Dokument 1.pdf (527 KB)
ps-Format:
Dokument 1.ps (938 KB)

Kurzfassung in Englisch

We consider a multicommodity routing problem, where demands are released
\emph{online} and have to be routed in a network during specified time
windows. The objective is to minimize a time and load dependent convex
cost function of the aggregate arc flow.

First, we study the fractional routing variant. We present two online
algorithms, called Seq and Seq$^2$. Our first main result states that,
for cost functions defined by polynomial price functions with nonnegative
coefficients and maximum degree~$d$, the competitive ratio of Seq and
Seq$^2$ is at most $(d+1)^{d+1}$, which is tight. We also present lower
bounds of $(0.265\,(d+1))^{d+1}$ for any online algorithm. In the case of
a network with two nodes and parallel arcs, we prove a lower bound of
$(2-\frac{1}{2} \sqrt{3})$ on the competitive ratio for Seq and Seq$^2$,
even for affine linear price functions. Furthermore, we study resource
augmentation, where the online algorithm has to route less demand than
the offline adversary.

Second, we consider unsplittable routings. For this setting, we present
two online algorithms, called U-Seq and U-Seq$^2$. We prove that for
polynomial price functions with nonnegative coefficients and maximum
degree~$d$, the competitive ratio of U-Seq and U-Seq$^2$ is bounded by
$O{1.77^d\,d^{d+1}}$. We present lower bounds of
$(0.5307\,(d+1))^{d+1}$ for any online algorithm and $(d+1)^{d+1}$ for
our algorithms.

Third, we consider a special case of our framework: online load balancing
in the $\ell_p$-norm. For the fractional and unsplittable variant of
this problem, we show that our online algorithms are $p$ and $O{p}$
competitive, respectively. Such results where previously known only for
scheduling jobs on restricted (un)related parallel machines.

Freie Schlagwörter (englisch): Online Optimization , Routing , Telecommunications
MSC - Klassifikation 90C25
MSC - Klassifikation 68W40
Abteilung: Optimierung
DDC-Sachgruppe: Allgemeines, Wissenschaft
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 07-22
ISBN: 1438-0064
Sprache: Englisch
Erstellungsjahr: 2007
Publikationsdatum: 13.08.2007
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: