2026-08-21T18:34:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27423 2026-08-21T14:42:39Z ddc:004 open_access

Forwarding Packets Greedily on the Line Boyar, Joan Favrholdt, Lene M. Larsen, Kim S. Schewior, Kevin van Stee, Rob Online algorithms Packet scheduling Greedy algorithm 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-2^{1-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joan Boyar and Lene M. Favrholdt and Kim S. Larsen and Kevin Schewior and Rob van Stee 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.42 urn:nbn:de:0030-drops-274230 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.42 eng https://creativecommons.org/licenses/by/4.0/legalcode