Competitive Online Multicommodity Routing
Please always quote using this URN: urn:nbn:de:0297-zib-9599
- In this paper we study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that only depends on the demands previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is 4K2 (1+K)2 -competitive, where K is the number of commodities. For the single-source single-destination 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: | 2007/06/14 |
Series (Serial Number): | ZIB-Report (07-16) |
ZIB-Reportnumber: | 07-16 |
Published in: | Appeared in: Theory of Computing Systems 45, No. 3 (2009), 533-554 |