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.
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 |