Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 3 of 10
Back to Result List

Competitive Online Multicommodity Routing

Please always quote using this URN: urn:nbn:de:0297-zib-9212
  • We study online multicommodity minimum cost routing problems in networks, where commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining the routing weights. We discuss an online algorithm that routes each commodity by minimizing a convex cost function that depends on the demands that are previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is $4K/2+K$-competitive, where $K$ is the number of commodities. For the parallel arc case this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Tobias Harks, Stefan Heinz, Marc PfetschORCiD
Document Type:ZIB-Report
Tag:Online Optimization; Routing; Telecommunications
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Date of first Publication:2006/05/30
Series (Serial Number):ZIB-Report (06-27)
ZIB-Reportnumber:06-27
Published in:Appeared in: T. Erlebach and C. Kaklamanis (eds.) Approximation and Online Algorithms (WAOA 2006). LNCS 4368, pp. 240-252, 2007
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.