921 eng reportzib 0 2006-05-30 2006-05-30 -- 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. 06-27 921 urn:nbn:de:0297-zib-9212 Appeared in: T. Erlebach and C. Kaklamanis (eds.) Approximation and Online Algorithms (WAOA 2006). LNCS 4368, pp. 240-252, 2007 Tobias Harks Stefan Heinz Marc Pfetsch 06-27 eng uncontrolled Online Optimization eng uncontrolled Routing eng uncontrolled Telecommunications Informatik, Informationswissenschaft, allgemeine Werke OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING ZIB Allgemein Heinz, Stefan https://opus4.kobv.de/opus4-zib/files/921/ZR-06-27.pdf https://opus4.kobv.de/opus4-zib/files/921/ZR-06-27.ps