2026/03/31 by Joan Boyar, Lene M. Favrholdt, Kim S. Larsen +2
Computer Science · #cs.DS
17 pages, 1 figure
arxiv created 2026/07/29 · arxiv updated 2026/07/31
We consider the problem of forwarding packets arriving online with their destinations in a line network. In each time step, each router can forward one packet along the edge to its right, and the packet arrives at the next router one time step later. Packets are forwarded until they reach their destination. The flow time of a packet is the elapsed time between its release and its arrival at its destination. The goal is to minimize the maximum flow time. This problem was introduced by Antoniadis et al. in 2014, with a focus on line networks. They proposed several natural algorithms. For one, they proved that it is not O(1)-competitive; for others, they claimed analogous lower bounds, seemingly leaving no natural candidate for an O(1)-competitive algorithm. In this paper, we study a natural algorithm not considered in that work. Our algorithm, simply called Greedy, selects packets according to their projected flow time under the assumption that they are not delayed any further. We focus on the special case in which each packet needs to be forwarded by one or two routers; this case captures core difficulties. We show that Greedy achieves a competitive ratio of exactly 2-21-k, where k is the number of active routers in the network. We also give the first nontrivial general lower bound, which applies even to randomized algorithms: using the same type of instances as in our lower bound for Greedy, we show that no algorithm can be (4/3-ε)-competitive for any ε>0.