@misc{HarksHeinzPfetsch, author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc}, title = {Competitive Online Multicommodity Routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9212}, number = {06-27}, abstract = {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.}, language = {en} } @misc{HarksHeinzPfetsch, author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc}, title = {Competitive Online Multicommodity Routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9599}, number = {07-16}, abstract = {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.}, language = {en} } @misc{Harks, author = {Harks, Tobias}, title = {Nash Equilibria in Online Sequential Routing Games}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9376}, number = {06-43}, abstract = {In this paper, we study the efficiency of Nash equilibria for a sequence of nonatomic routing games. We assume that the games are played consecutively in time in an online fashion: by the time of playing game \$i\$, future games \$i+1,\dots,n\$ are not known, and, once players of game \$i\$ are in equilibrium, their corresponding strategies and costs remain fixed. Given a sequence of games, the cost for the sequence of Nash equilibria is defined as the sum of the cost of each game. We analyze the efficiency of a sequence of Nash equilibria in terms of competitive analysis arising in the online optimization field. Our main result states that the online algorithm \$\sl {SeqNash}\$ consisting of the sequence of Nash equilibria is \$\frac{4n}{2+n}\$-competitive for affine linear latency functions. For \$n=1\$, this result contains the bound on the price of anarchy of \$\frac{4}{3}\$ for affine linear latency functions of Roughgarden and Tardos [2002] as a special case. Furthermore, we analyze a problem variant with a modified cost function that reflects the total congestion cost, when all games have been played. In this case, we prove an upper bound of \$\frac{4n}{2+n}\$ on the competitive ratio of \$\sl {SeqNash}\$. We further prove a lower bound of \$\frac{3n-2}{n}\$ of \$\sl {SeqNash}\$ showing that for \$n=2\$ our upper bound is tight.}, language = {en} } @misc{Wolf, author = {Wolf, Thomas}, title = {A Study of Genetic Algorithms solving a combinatorial Puzzle}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3445}, number = {SC-98-01}, abstract = {The suitability of Genetic Algorithms (GAs) to solve a combinatorial problem with only one solution is investigated. The dependence of the performance is studied for GA-hard and GA-soft fitness functions, both with a range of different parameter values and different encodings.}, language = {en} }