{'fraction_non_alphanumeric': 0.043696424837967804, 'fraction_numerical': 0.013589797198411038, 'mean_word_length': 4.011787819253438, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Pony Express Communication Problem

We introduce a new problem which we call the Pony Express problem. n robots with differing speeds are situated over some domain. A message is placed at some commonly known point. Robots can acquire the message either by visiting its initial position, or by encountering another robot that has already acquired it. The robots must collaborate to deliver the message to a given destination. The objective is to deliver the message in minimum time. In this paper we study the Pony Express problem on the line where n robots are arbitrarily deployed along a finite segment. The robots have different speeds and can move in both directions. We are interested in both offline centralized and online distributed algorithms. In the online case, we assume the robots have limited knowledge of the initial configuration. In particular, the robots do not know the initial positions and speeds of the other robots nor even their own position and speed. They do, however, know the direction on the line in which to find the message and have the ability to compare speeds when they meet. First, we study the Pony Express problem where the message is initially placed at one endpoint of a segment and must be delivered to the other endpoint. We provide an O(n log n) running time offline algorithm as well as an optimal online algorithm. Then we study the Half-Broadcast problem where the message is at the center and must be delivered to either one of the endpoints of the segment [-1,1]. We provide an offline algorithm running in O(n^2 log n) time and we provide an online algorithm that attains a competitive ratio of 3/2 which we show is the best possible. Finally, we study the Broadcast problem where the message is at the center and must be delivered to both endpoints of the segment [-1,1]. Here we give an FPTAS in the offline case and an online algorithm that attains a competitive ratio of 9/5, which we show is tight.


Introduction
The Pony Express refers to the well-known mail delivery service performed by continuous horse-and-rider relays between a source and a destination point. It was employed in the US for a short period (1860 to 1861) to deliver mail between Missouri and California.
The problem considered in this paper is motivated by the above. If one thinks of the horses as robots of differing speeds operating over a continuous domain then the Pony Express can serve as a suitable paradigm for message delivery from a source to a destination by robots passing messages from one robot to the next upon contact. In particular, consider the following problem: Initially a piece of information is placed at a certain location, referred to as the source. A group of robots are required to deliver the information from the source to another location referred to as the destination. The problem is one of designing a message delivery algorithm that delivers the message by selecting a sequence of robots and their movements that relay the message from a source to a destination in optimal time. This is the full version of a paper to appear at IWOCA 2021 6 We restrict our attention to message transmission rather than package delivery, which differs from message transmission in that packages cannot be replicated.
As will be seen, designing such algorithms can be a challenge given that the robots do not necessarily have the same speed and the overall delivery time may depend on what knowledge the agents possess concerning the location and speeds of the other robots. Further, the communication exchange model is face-to-face (F2F) in that two robots can exchange a message only when they are at the same location at the same time.
The problem itself can be studied over any domain. In this paper, we restrict our attention to a finite interval which already offers some interesting questions to resolve.

Model
We consider a set R of n robots initially scattered along a finite interval. Each robot r has a speed v(r) and unique initial position p(r). Note that robots with the same initial position can be handled through some tie-breaking mechanism, adding minor perturbations to the robots' positions, etc. The goal is to use the robots to deliver a message to one or both of the interval endpoints. Robots acquire the message through face-to-face contact either with the message at its initial location, or by encountering another robot with the message. We consider three variants of the Pony Express problem in which the message is initially placed at the point 0. In each case, the goal is to solve the problem in the minimum amount of time. We consider both the offline and online settings. In the offline setting, all information regarding the robots (their initial positions and speeds) are available and a centralized algorithm provides a sequence of robot meetings that relay the message from the source to the destination(s) in optimal time.
In the online setting, we consider a model where robots do not know their own location nor their own speeds. Further, the agents do no have any information about other agents (initial positions, speeds) or even the number of robots in the system. The robots do however know the direction of the origin from their current position. When two robots meet, they can compare their speeds and decide which is faster.
To measure the performance of our online algorithms, we consider their competitive ratios. Let t * (I) be the optimal delivery time for an instance I of a given problem and t A (I) be the time needed by some online algorithm A for the same instance. Then the competitive ratio of A is Our goal is to find online algorithms that minimize this competitive ratio.

Related work
There are many applications in a communication network where message passing (see [6]) is used by agents so as to solve such problems as search, exploration, broadcasting and converge-casting, connectivity, and area coverage. For example, the authors of [4] address the issue of how well a group of collaborating robots with limited communication range is able to monitor a given geographical space. In particular, they study broadcasting and coverage resilience, which refers to the minimum number of robots whose removal may disconnect the network and result in uncovered areas, respectively. Another application may be patrolling whereby many agents are required to keep perpetually moving along a specified domain so as to minimize the time a point in the domain is left unvisited by an agent, e.g., see [10] for a related survey. A general energy-aware data delivery problem was posed by [1], whereby n identical, mobile agents equipped with power sources (batteries) are deployed in a weighted network. Agents can move along network edges as far as their batteries permit and use their batteries in linear proportion to the distance traveled. At the start the agents possess some initial information which they can exchange upon meeting at a node. The authors investigate the minimal amount of power, initially available to all agents, necessary so that convergecast may be achieved. They study the question in the centralized and the distributed setting.
Two related communication problems: data delivery and convergecast are presented for a centralized scheduler which has full knowledge of the input in [9]. The authors show that if the agents are allowed to exchange energy, both problems have linear-time solutions on trees but for general undirected and directed graphs they show that these problems are NP-complete.
A restricted version of the problem above concerns n mobile agents of limited energy that are placed on a straight line and which need to collectively deliver a single piece of data from a given source point s to a given target point t on the line. In [5] the authors show that the decision problem is NP-hard for a single source and also present a 2-approximation algorithm for the problem of finding the minimum energy that can be assigned to each agent so that the agents can deliver the data. In [7] it is shown that deciding whether the agents can deliver the data is (weakly) NP-complete, while for instances where all input values are integers, a quasi-, pseudo-polynomial time algorithm in the distance between s and t is presented.
Additional research under various conditions and topological assumptions can be found in [2] which studies the game-theoretic task of selecting mobile agents to deliver multiple items on a network and optimizing or approximating the total energy consumption over all selected agents, in [3] which studies data delivery and combines energy and time efficiency, and in [11,12] which is concerned with collaborative exploration in various topologies.
The focus of our current study is on finding offline and online algorithms for message delivery from a source to a destination on a line segment where the goal is to minimize the time needed. This differs from the work outlined above which focuses on energy transfer and consumption to perform either a delivery or broadcast. To the best of our knowledge, the problem and analysis considered in this paper has not been considered before.

Outline and results of the paper
In Section 2 we discuss the Pony Express variant of the problem and present optimal online and offline algorithms. In Section 3, we discuss the Half-Broadcast variant of the problem. We provide an optimal offline algorithm and an online algorithm with a 3 2 competitive ratio and show this ratio is the best possible. In Section 4, we discuss the Broadcast variant of the problem and provide an online algorithm with a competitive ratio of 9 5 which we show is the best possible. We also present an offline FPTAS for the Broadcast variant. (Note: the offline algorithm is not exact but depends upon performing binary search over a real interval).

Pony Express
In this section, we discuss the solution for the Pony Express variant of the problem over the segment [0, 1], wherein the message is placed initially at 0 and must be delivered to 1.

Online
First, we propose an online algorithm for the Pony Express variant. The robots start at the same time and move towards the origin. The first robot to reach 0 acquires the message. A slower robot with the message meeting a faster one, transfers the message to the faster which then moves towards 1. The algorithm is as follows.
Algorithm 1 Pony Express Online Algorithm 1: All robots start at the same time and move with their own speeds towards the endpoint 0; 2: if a robot r reaches 0 then 3: robot r acquires the message and moves towards 1; 4: if a robot with the message r meets a robot r such that v(r) < v(r ) then 5: robot r transmits the message to robot r ; 6: robot r changes direction and moves towards 1; 7: else 8: continue moving; 9: Stop when destination 1 is reached; Next we prove the optimality of Algorithm 1. Proof. Let m i be the i th handover point between robots r i−1 and r i at time t i . Observe that since r i−1 participated in the i − 1 th handover, it must be slower than r i , or v(r i−1 ) < v(r i ) (or else there would not be a handover). For simplicity and consistency of notation, let r 0 be an additional robot with initial position and velocity 0. In other words, robot r 0 simply holds the message at its initial position until robot r 1 arrives at 0 to perform the first handover. Note this does not change the problem at all, since robot r 0 will not carry the message any distance.
We show by induction and use the following inductive hypothesis: "Each participating robot r to the left of m i has speed v(r) < v(r i ) and t i is the earliest time the message can be delivered to m i ." We say the message is delivered to a point m as soon as any robot that has acquired the message (excluding the additional robot r 0 ) reaches point m.
For the base case consider m 1 . Observe robot r 1 is the first robot to reach the source, since any robot with speed greater than 0 would satisfy the condition to participate in a handover. It is clear then, that every robot to the left of m 1 = 0 has speed less than v(r 1 ), since otherwise it would not be the first to arrive at 0. Also, t 1 is the first time the message is delivered to 0 since r 1 is the first robot to arrive at 0.
Assume the inductive hypothesis holds for m i−1 . Observe that since there is a handover at m i , v(r) < v(r i−1 ) < v(r i ) for all robots r to the left of r i−1 . Therefore, all participating robots to the left of m i are slower than r i−1 . Furthermore, the message reaches m i at the earliest possible time, since otherwise a slower robot must not have handed the message over to a faster available robot. Finally, observe that it is the fastest robot delivers the message to the destination point.

Offline
In this section, we present an offline algorithm for computing the optimal delivery time for the Pony Express variant (see Algorithm 2). In the previous section, we discussed the behavior of the robots in an optimal solution (i.e. they move toward 0 until encountering the message and then turn around and move toward the endpoint). The goal for an offline algorithm, then, is to compute all the meeting points where a handover occurs. We could consider all n 2 possible meeting points, but that would be inefficient. The key observation is that every robot must encounter one of its neighbors (either from its left or from its right) before encountering any other robot. When two robots meet, either both robots are moving toward 0 (and neither have the message) or one robot is traveling toward the endpoint with the message and the other is traveling toward 0 to acquire it. In either case, the meeting robots' neighbors and/or directions change, so new meeting points must be computed. This is the idea behind the algorithm. We keep track of potential O(n) meeting points in a priority queue and examine them one-by-one to see how they affect the system. Theorem 2.2. Algorithm 2 finds an optimal solution to the Pony Express problem and runs in O(n log n) time.
Proof. Observe that q is a Priority Queue whose operations add(r, p) for adding element r with a priority p, remove(r) for removing element r from the queue, remove front() for removing and returning the element with the highest priority, and update(r, p) for updating an element's priority in the queue each have a time-complexity of O(log n).
In the first step of the algorithm, each robot is added to the priority queue, using its meeting time with its left-hand neighbor as a priority. Note this could be ∞ if the robot's left-hand neighbor either does not exist or moves at a faster speed away from it. This step has time-complexity O(n log n).
Next, notice on each iteration of the loop in line 15, the size of the queue is decremented by at least one and thus terminates after at most n iterations. Therefore this part of the algorithm has time complexity O(n log n).
Finally, observe that robots change direction if and when they meet a slower robot with the message and meeting times are updated appropriately when a change in direction occurs. This behavior is equivalent to that of Algorithm 1 and therefore is optimal by Theorem 2.1.
Algorithm 2 returns only the final delivery time of the message to its destination. Observe though, that the algorithm could easily be made to return the entire sequence of handover meeting times (each r.meet in line 18).

Half-Broadcast
In this section we consider the Half-Broadcast variant of the problem in which a message initially placed at 0 must be delivered to one of the endpoints of the interval [−1, 1].

Online
First, we show a lower bound of 3 2 on the competitive ratio for any algorithm to solve this problem.
Theorem 3.1. The competitive ratio for the Half-Broadcast problem is at least 3 2 .
Proof. Consider two robots r and r with speeds v(r) = 1 2 and v(r ) = 1. Initially r is placed at p(r) = 0. The initial position of r , p(r ) will be determined below. Let A be any online algorithm for two robots. Observe the movement of r during the time period [0, 1]. Without loss of generality, assume that the final position of r in this time period is x ∈ 0, 1 2 . In this case, we let p(r ) = −1. (Note that if r ends up in 0, − 1 2 , we let p(r ) = 1 and a symmetric argument will follow.) Observe that the trajectories taken by r and r cannot overlap during the time period [0, 1]. Indeed, at (as it must reach x by time 1) and r is in the range [−1, −1 + t]. These ranges do not overlap for x ∈ 0, 1 2 and t ∈ [0, 1] except at x = 0 and t = 1, in which case both robots are at 0 at time 1. Thus it is not possible for r to receive the message before time 1. At time 1, r is at x ∈ 0, 1 2 and can not make it to either endpoint (−1 or 1) sooner than time 2. Let the position of r be −y ∈ [−1, 0] at time 1. If r receives no help from r when delivering the message then it cannot obtain the message before an additional y units of time to travel from −y to the message source 0 and 1 unit of time to bring the message to either endpoint, i.e., 2 + y ≥ 2 (y ≥ 0 units of time). If r does receive help from r, it cannot receive the message before time x−y 3 2 and deliver the message before time 1 + 1 + 2(x−y) 1 2 ] and y ∈ [−1, 0]. Thus any online algorithm A must take time at least 2 units of time to solve this instance of the problem. But the optimal offline algorithm can complete the task in time 4 3 by having the two robots meet at time 2 3 at position − 1 3 and then having r deliver the message to −1. Therefore the competitive ratio for any algorithm is at least 3 2 .
Next we provide an online algorithm that achieves the competitive ratio 3 2 . We consider the very simple algorithm that essentially partitions the line segment (and robots) into two instances of the Pony Express Problem (over [−1, 0] and [0, 1]) solves them independently. The delivery time is given by whichever instance delivers the message first.

Algorithm 3 Half-Broadcast Online Algorithm
1: All robots start at the same time and move within their own subinterval at their own speeds towards the endpoint 0; 2: if a robot r reaches 0 then 3: robot r acquires the message and moves towards the endpoint closest to its original position; 4: if a robot with the message r meets a robot r such that v(r) < v(r ) then 5: robot r transmits the message to robot r ; 6: robot r changes direction and moves towards the nearest endpoint; 7: else 8: continue moving; 9: Stop when either endpoint is reached by robot; First, we show that Algorithm 3 guarantees a competitive ratio of 3 2 when only two robots participate. Then, we extend the result to systems of n robots. Note that our algorithm is clearly optimal in the case where there is only one robot. Proof. Consider two robots r and r . Without loss of generality, assume that v(r) ≤ v(r ) and that in the optimal algorithm the message is delivered at 1. Considering an optimal algorithm, observe that either robot r delivers the message without any help or both collaborate to deliver the message. In the second case, suppose that m is the optimal meeting point between robots r and r . Since v(r) ≤ v(r ), r must deliver the message. Thus, the delivery time is at least Observe that in cases where either robot delivers the message without collaboration, Algorithm 3 is optimal. If the optimal algorithm requires the two robots to collaborate, however, Algorithm 3 is not optimal. Observe that the algorithm terminates when either of the two robots arrives at an endpoint. Therefore, the delivery time is maximized when |p(r)|+1 v(r) = |p(r )|+1 v(r ) . Thus, the competitive ratio is given by: Observe that p(r) = 0 and p(r ) = 1 maximizes the ratio. Thus, the competitive ratio is at most 2v(r) mv(r )+v(r) (1−m) and v(r ) = 2v(r). Then: Since 2v(r) = v(r ), m = 1 3 and the competitive ratio is bounded by 3/2 for any chosen speed of v(r ). Now we are ready to present the main result of the section in the following theorem. We show that the competitive ratio of Algorithm 3 for the Half-Broadcast problem is at most 3 2 when n robots are participating. By Theorem 3.1, this is best possible.
Theorem 3.2. The competitive ratio of Algorithm 3 is at most 3 2 for systems of n robots. Proof. Without loss of generality, assume that the message is delivered to 1 in both the online and optimal offline algorithm. (Otherwise a symmetric argument can be used.) Let µ 1 , µ 2 , . . . , µ k be the k < n meeting points of the optimal centralized algorithm where robot r π(i) carries the message between µ i−1 and µ i . Let µ 0 = 0. Let m 1 , m 2 , . . . m l be the l < n meeting points of the Algorithm 3 where robot r σ(i) traverses between m i−1 and m i . Let m 0 = 0. The competitive ratio of our algorithm is Observe that m l ≤ µ k since Algorithm 3 does not attain optimal time. Therefore, 1−m l v(r σ(l) ) ≤ µ k −m l v(r π(k−1) ) + 1−µ k v(r π(k) ) since v(r π(k−1) ) < v(r π(k) ). Observe then, that we can trim the interval at m l and solve the problem with n − 1 robots. The key observation is that the online algorithm is actually "faster" at each intermediate handover except for the first handover. In other words, the first handover is the only segment that hurts the online algorithm. We have shown that the competitive ratio of the new problem is less than or equal to the competitive ratio of the original problem and therefore by induction (with Lemma 3.1 as the base case) the result follows.

Offline
Next, we show an offline algorithm for computing the optimal solution. To do this, we make use of Algorithm 2, the offline algorithm for the Pony Express problem. First we need the following lemma: Proof. Observe that the message must travel to one of the endpoints and therefore must traverse the entirety of one of the half-intervals. This means the message must encounter every robot on that half-interval, and so either r or r must encounter the message. Suppose, without loss of generality, that the message is delivered to 1 in an optimal solution. Then consider the moment that r encounters the message with another robotr. Observe that, since r is the fastest robot with initial position on (0, 1],r can only be faster than r if its initial position was on [−1, 0), in which casê r could deliver to −1 in less time, a contradiction.
In an optimal solution, robots that initially start in the interval [−1, 0] can participate in the message delivery at the point 1, or vice-versa. The following lemma shows that even if many robots that initially start in an opposite interval can participate in delivering the message, there is always an identical solution where only one robot in the opposite interval participates in delivering the message.

Lemma 3.3.
There is an optimal solution such that at most one robot from the interval that does not contain the delivered-to endpoint participates.
Proof. Observe that since the message is delivered to 1, the optimal algorithm involves all participating robots moving toward the center and then, upon encountering the message (either at the center or from a carrying robot), moving towards 1. Note that robots on the subinterval [−1, 0] move in one direction while robots on the subinterval (0, 1] travel some distance toward 0 and then turn around. Observe also that the fastest robot on the interval [0, 1], say r, must deliver the message by Lemma 3.2. Suppose, by contradiction, robots r and r 2 from [−1, 0) participate in the optimal algorithm. Let d 1 > d 2 (r 2 is closer to 0 than r ), then v(r ) > v 2 , or else r can never catch up to r 2 and will never encounter any robots that r 2 has not already encountered (and thus not participate). Furthermore, in order to participate, r must be so much faster than r 2 that it passes r 2 and encounters a faster robot on the right that has not yet encountered the message. In this case, however, r 2 , may as well have not participated at all. Therefore, r 2 's participation does not improve the delivery time. Proof. Without loss of generality, assume that in the optimal solution, the message is delivered to +1 (we can compute solutions for both the problem and its reflection). Therefore, according to Lemma 3.3, at most one robot with initial position on the interval [−1, 0) need participate in the message's delivery. Observe that if a robot l with initial position p(l) ∈ [−1, 0) helps, the delivery time would be equivalent if l were reflected about 0 and all robots with speed less than v(l) removed, since, in order for l to participate, it must pass 0 and encounter either the endpoint or a faster robot at a meeting point m (rendering all slower robots that reach m afterwards useless). Given the full set of robots R, let v(r) be the speed of robot r, p(r) be the initial position of robot r, and L = {r ∈ R|p(r) < 0}. Also, let |r| be a copy of the robot r, such that v(|r|) = v(r) and p(|r|) = |p(r)|. Let PonyExpress(R ⊆ R) be the solution for the Pony Express variant of the problem with the robots in R . Observe the solution for the Half-Broadcast problem is: This minimization is computable with time-complexity O(n 2 log n), since Algorithm 2 must be run for every robot in L.

Broadcast
In this section we study the Broadcast variant of the problem. Recall that in the Broadcast problem, a message initially placed at 0 must be delivered by robots to both endpoints of the interval [−1, 1] in minimum time. We begin with the following lemma: There is an optimal solution such that at most one robot participates in the message's delivery to both endpoints.
Proof. Suppose for the sake of contradiction that both robots r and r deliver the message to participating robots in each delivery (to −1 and to 1). Let t −1 and t −1 be the times that r and r hand the message over to robots participating in delivery to −1. Similarly, let t 1 and t 1 be the times that r and r hand the message over to robots participating in delivery to 1.
Suppose, without loss of generality, that r participates in the last of these four handovers for deliver to 1, or t 1 > t −1 , t −1 , t 1 . Then r must have passed the robot that r handed the message over to at t 1 (sayr), otherwise it would never handover the message to a new robot, and would not participate in the delivery to 1. In this case, though, robotr need not participate anymore, since a faster r delivers the message to a faster robot closer to 1. This is a contradiction to the statement that both robots participate in both deliveries.

Online
First we show that the competitive ratio of any online algorithm is at least 9 5 .
Theorem 4.1. The competitive ratio for any Algorithm that solves the Broadcast problem is at least 9 5 . Proof. Consider two robots, r with speed 1 and initial location 0 and r with speed and initial location to be determined below. Let A be any online algorithm for two robots. Observe the movement of r during the time period [0, 1] under algorithm A. Without loss of generality, assume the final position of r is x ∈ [−1, 0] and let y be the furthest that r progressed into [0, 1] during this time period. Observe that 0 ≤ y ≤ 1 2 since r is in [−1, 0] at time 1. Let a = 1−y 2 . In this case, we set the r 's speed v(r ) = a and its initial position p(r ) = y + a (Figure 4.1). A symmetric argument can be used in the case that x ∈ [0, 1].
Observe that the trajectories of r and r do not overlap in the time period [0, 1] for any x ∈ [−1, 0] and y ∈ 0, 1 2 with the exception of the case where y = x = 0 and t = 1. Indeed, r can only reach the position y at time 1. Prior to that time, its position must be to the right of y and therefore to the right of r. At time 1 it may reach y but by that time r is at x ≤ 0. The only overlap occurs when x = y = 0.
At time 1, r is at position z ≥ y ≥ 0. In order to deliver to the message to either end point, it must take time at least 1+z a ≥ 2(1+y) 1−y ≥ 2 + 2y. Thus, if r is the first to deliver the message to one of the end points, the algorithm must take at least time 3 + 2y. On the other hand, if r is to deliver the message to both end points, it must take at least time y to reach position y, a further time y to return to 0, plus an additional time 3 to reach both end points. Therefore, the online algorithm A must take time at least 3 + 2y to solve this instance of the problem. (The case where r delivers the message to both endpoints is clearly worse.) Consider the following (offline) algorithm for the above instance: r and r meet at position y+a 1+a at time y+a 1+a (they move toward each other until meeting). Then r delivers the message to -1 in a further y+a 1+a + 1 for a total of 1 + 2(y+a) 1+a time. And r delivers the message to 1 in a further y+a 1+a + 1−y−a a = y+a 1+a + 1 for a total of 1 + 2(y+a) 1+a time. Therefore, the competitive ratio of algorithm A on this instance is at least 3+2y 1+ 2(y+a) 1+a = (3+2y)(3−y) 5+y ≥ 9 5 for y ∈ [0, 1 2 ]. Now we show that there is an online algorithm that attains this competitive ratio. Algorithm 4 is very similar to the Half-Broadcast algorithm, in that we essentially partition the line segment (and robots) into two instances of the Pony Express Problem (over [−1, 0] and [0, 1]). The difference is that every time a robot participates in a handover (at the source, endpoint, or with another robot), it turns around and moves in the opposite direction. This is necessary to ensure the message is delivered to both endpoints (consider the case where all robots start on one side of the message).

Algorithm 4 Broadcast Algorithm
1: All robots start at the same time and move within their own subinterval at their own speeds towards the endpoint 0; 2: if a robot r reaches 0 then 3: robot r acquires the message and moves towards the endpoint closest to its original position; 4: if a robot with the message r meets a robot r such that v(r) < v(r ) then 5: robot r transmits the message to robot r , changes direction, and continues moving towards the opposite endpoint; 6: robot r changes direction and moves towards the nearest endpoint; 7: else 8: continue moving; 9: if a robot with the message r reaches the endpoint the opposite endpoint then 10: robot r changes direction and continues moving; 11: Stop when both endpoints have been reached by robot; Lemma 4.2. The competitive ratio of Algorithm 4 for the case n = 2 is at most 9 5 .
Proof. Consider robots r and r with initial positions p(r) and p(r ) and speeds v(r) and v(r ), respectively. Without loss of generality, assume that v(r) ≤ v(r ). Observe that, in any optimal algorithm, either one robot delivers the message to both sides without collaboration, each robot delivers the message without any collaboration, or each robot delivers the message and collaborates. In the third case, suppose that m is the meeting point. Without loss of generality, we assume that m ≥ 0. Further, since v(r ) ≥ 0, we can assume that r does not stop until it meets r. Thus, the deliver time is at most Now consider the delivery time of Algorithm 4. Without loss of generality, assume that p(r) > p(r ). We consider two cases, the case where p(r) ≥ 0 and p(r ) ≤ 0 and the case where p(r) ≤ 0 and p(r ) ≤ 0.
Let us first consider the case where p(r) ≥ 0 and p(r ) ≤ 0. The case where p(r) ≤ 0 and p(r ) ≥ 0 is analogous. Observe that if in the optimal algorithm both deliver the message without help or only one delivers the message to both sides without help then Algorithm 4 attains optimal deliver time. It is sufficient, then, to consider the case where, optimally, each delivers the message to an endpoint after collaboration ( Figure 2). Therefore, the competitive ratio is given by Observe that the competitive ratio is maximum when m+|p(r )| v(r ) is maximum, which . We can rewrite the competitive ratio as: .
Observe that the values of y and p(r ) that maximize the competitive ratio are y = 0 and p(r ) = 0 so that the competitive ratio is bounded by: .
To maximize the competitive ratio, we maximize min 1+x which results in x = 1 3 . Hence, v(r ) v(r) = 2 and we can compute the maximum competitive ratio as It remains to show the case where p(r) ≤ 0 and p(r ) ≤ 0. Observe that if in the optimal algorithm robots collaborate to deliver the message, then Algorithm 4 attains the optimal time since both are in the same segment. However, if in the optimal algorithm each robot delivers the message to one side, then Algorithm 4 cannot attain optimal time ( Figure 3). Therefore, the competitive ratio is given by where t is the time that robots need to meet and return to the original location. To maximize the competitive ratio, we maximize t = |p(r)−p(r )| v(r)+v(r ) by assigning the extreme values to r and r, i.e., r = −1 and r = 0. Moreover, we maximize the competitive ratio by setting 1−p(r) v(r) = 3+p(r ) v(r ) . Therefore, v(r ) v(r) = 3+p(r ) r+1 = 2 and t = 1 3v(r) and the competitive ratio is bounded by Next, we show that Algorithm 4 attains optimal competitive ratio with n ≥ 3 robots.
Theorem 4.2. The competitive ratio of Algorithm 4 for systems of n robots is at most 9 5 . Proof. Let µ + 1 , µ + 2 , . . . µ + k + and µ − 1 , µ − 2 , . . . µ − k be the k + ≤ n and k − ≤ n meeting points of the optimal centralized algorithm of the robots that carry the message to 1 and −1 respectively where robot r + π(i) and r − π(i) carries the message between µ + i−1 and µ + i and µ + i and µ + i−1 , respectively. Let µ + 0 and µ − 0 = 0. Let m + 1 , m + 2 , . . . m + k + and m − 1 , m − 2 , . . . m − k be the l + ≤ n and l − ≤ n meeting points of the Algorithm 4 of the robots that carry the message to 1 and −1 respectively where robot r + σ(i) and r − σ(i) carry the message between m + i−1 and m + i and m − i and m − i−1 , respectively. Let m + 0 and m − 0 = 0 Then the competitive ratio of our algorithm is .
We claim that v(r + σ(l + ) ) ≥ v(r + π(k + ) ) and v(r − σ(l − ) ) ≥ v(r − π(k − ) ). Indeed, if the fastest robot in each side delivers the message in Algorithm 4, then v(r + σ(l + ) ) = v(r + π(k + ) ) and v(r − σ(l − ) ) = v(r − π(k − ) ). Otherwise, we claim that in Algorithm 4, the fastest robot delivers the message to both sides. The key observation is that when the fastest robot gets the message, it never hands it over to another robot and that it is nearest to the endpoint that is delivered to first. To see the latter, if the fastest robot is on the other side, it would take at most 2 v where v is the speed of the fastest robot. Therefore, it arrives earlier and v(r + σ(l + ) ) = v(r + π(k + ) ) and v(r − σ(l − ) ) = v(r − π(k − ) ). Therefore, the fastest robot delivers the message in one side and then reaches the other side by itself. Observe that m + l + ≤ µ + k + and m − l − ≥ µ − k − since Algorithm 3 does not attain optimal time. Therefore, π(k) ) since v(r + π(k + −1)) < v(r + π(k + ) ) and v(r − π(k − −1) ) < v(r − π(k + −) ). Therefore, we can trim the line at max m + l + , |m − l − | and solve the problem with n − 1 robots and we have shown the competitive ratio of the smaller problem is less than or equal to the original problem.
The theorem follows inductively with Lemma 4.2 acting as the base case.

Offline
In this section, we provide an offline fully polynomial time approximation scheme (FPTAS).
Theorem 4.3. For any > 0, there exists an algorithm for finding a solution to within an additive factor of of optimal to the Broadcast problem with running time O(n 2 log n log 1 ).
Proof. According to Lemma 4.1, at most one robot must cross 0 and participate in the message's delivery to both endpoints. This robot, say r, may participate by delivering the message itself or handing it over to another robot. It's important to note that the receiving robot may not be the first encountered by r nor must it be faster than r. We must consider the scenarios where r delivers the message to each of the possible robots on the opposite subinterval. To facilitate the formulation of the solution, we assume there are robots with speed 0 at both endpoints −1 and 1 so that delivering to these robots is equivalent (in time and meaning) to delivering to the destination. Suppose the optimal handover on the opposite side of the interval occurs at position m on the segment. Then, observe that since all robots must only participate in delivering the message to the nearest endpoint, there are essentially two instances of the regular PonyExpress problem to solve (one for each endpoint). One instance is on the interval [−1, min(m, 0)] and the other [max(m, 0), 1]. Also, the robots have shifted some distance toward 0, based on their speeds. This new instance can be constructed in linear time and solved in O(n log n) time by Algorithm 2.
All that remains, then, is to find m. Observe that two robots l and r with initial positions p(l) and p(r), and speeds v(l) and v(r), respectively can meet at any point on the interval 0, min 1, p(r) − p(l) v(l) − v(r) .
So the optimal solution can be described as: PonyExpress T R, m − p(l) v(l) , m .
Notice the inner minimization is over a real domain where the function is bitonic and so it can be estimated using binary search. The runtime for this is therefore O(n 2 log n log 1 ) where the computed meeting point is within of the optimal meeting point.

Conclusion
In this paper, we have introduced the Pony Express problem. We considered the case where the domain of interest is a line segment and the cases where a message must be delivered from one end to the other (Pony Express), from the center to one of the end points (Half-Broadcast) and from the center to both end points (Broadcast). For the first two problems we provide polynomial time offline algorithms and for the third an FPTAS. We provide online algorithms for each problem with best possible competitive ratio in each case.
A number of open problems are suggested by our study. First, it seems likely the the runtime of our offline algorithms may be improved at least for the case of Half-Broadcast and Broadcast and that an exact algorithm exists for Broadcast. Second, it might be worth considering variations on the amount and type of information available to the agents in the online setting. Finally, another direction of study would be to consider domains other than a finite interval. Preliminary results for the plane can be found in [8].