Forwarding Packet Greedily on the Line.

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Kevin Schewior, and Rob van Stee.
In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS), Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH. Accepted for publication.

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. Each packet that is forwarded 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 difference between its release time and the time of its arrival at its destination. The goal is to minimize the maximum flow time.

This problem was introduced by Antoniadis et al. in 2014, who also focus on line networks. They propose a collection of natural algorithms and prove for one, and claim for others, that none of them are O(1)-competitive, seemingly leaving no natural algorithm as a candidate for being O(1)-competitive.

In this paper, we propose an algorithm which the previous work seems to have missed. Our algorithm, simply called GREEDY, selects packets based on their projected flow time assuming they are not delayed any further. We consider the special case where each packet needs to be forwarded by exactly one or two routers, a special case that 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, even for randomized algorithms: Using the same type of instances as in our lower bound for GREEDY, we were able to show that no algorithm can be \( (4/3-\varepsilon) \)-competitive for any \( \varepsilon>0 \).

---

open access (364 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.