PACKET ROUTING: COMPLEXITY AND ALGORITHMS
BRITTA PEIS, MARTIN SKUTELLA, AND ANDREAS WIESE
Abstract. Store-and-forward packet routing belongs to the most fundamen-
tal tasks in network optimization. Limited bandwith requires that some pack-
ets cannot move to their destination directly but need to wait in intermediate
nodes on their path or take detours. It is desirable to find schedules that en-
sure fast delivery of the packets, in particular for time critial applications. In
this paper we investigate the packet routing problem theoretically. We prove
that the problem cannot be approximated with a factor of 6/5−²for all ² > 0
unless P=NP. We show that restricting the graph topology to planar graphs
or even directed trees still does not allow a PTAS.
We present three individual algorithms for packet routing on trees: For
undirected trees we give a factor 2 approximation. For directed trees we show
that the path coloring problem can be solved optimally in polynomial time.
Based on this, we show how to construct a schedule with length C+D−1
where Cand Ddenote the trivial lower bounds congestion and dilation. If the
lengths of the paths of the packets are pairwise different, we can compute a
schedule of length Don directed trees which is optimal. For all cases we show
that our analysis is tight. Finally, we show that it is NP-hard to approximate
the packet routing problem with an absolute error of kfor any k≥0.
1. Introduction
In this paper we study the packet routing problem. Given a set of packets in a
network originating at possibly different start vertices we want to transfer them to
their respective destination vertices. The goal is to minimize the overall makespan,
that is the time when the last packet arrives at its destination. We consider the
offline version of the problem where all information about the network and the
packets, in particular the start- and destination vertices are given in advance. In
our routing model, we assume store-and-forward routing. This means that every
node can store arbitrarily many packets but each link (a directed or undirected
edge) can be used by only one packet at a time. We study the case where the paths
of the packets are fixed in advance as well as the case where their computation
is part of the problem. Moreover, we distinguish between different types of the
underlying graphs, e.g., directed graphs, undirected graphs, planar graphs or trees.
This has important applications in all settings where packets need to be trans-
fered through a network. In computer networks like local area networks (LANs) or
the internet many data packets need to be routed. The priority of the packets in
the schedule is not immediately clear and inappropriate routing rules can lead to
ineffective schedules. Delay due to packet latency is not desirable. In particular,
time-critial applications like voice over IP (VoIP) need their packets to be delivered
within a certain time frame in order to work accurately. Therefore we are interested
in schedules that guarantee the packets to arrive at their respective destinations
1
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 2
as early as possible. Finding such effective schedules in distributed systems is a
challenging task.
1.1. Packet Routing Problem. The packet routing problem is defined as follows:
Let G= (V, E)be a directed or undirected graph. A packet Mi= (si, ti)is a
tupel consisting of a start vertex si∈Vand a destination vertex ti∈V. Let
M={M1, M2, M3, ..., MN}be a set of packets.
Then (G, M)is an instance of the packet routing problem with variable paths.
The problem has to parts: First, for each packet Miwe need to find a path Pi=
(si=v0, v1, ...v`−1, v`=ti)from sito tisuch that {vi, vi+1} ∈ Eif Gis undirected
or (vi, vi+1)∈Eif Gis directed for all iwith 0≤i≤`−1. Assuming that it takes
one timestep to send a packet along an edge we need to find a routing schedule for
the packets such that
•each message Mifollows its path Pifrom sito tiand
•each edge is used by at most one packet at a time
We assume that time is discrete and that all packets take their steps simultaneously.
The objective is to minimize the makespan, i.e., the time when the last packet has
reached its destination vertex. For each packet Miwe define Dito be the length of
the shortest path from sito ti, assuming that all edges have unit length. Moreover,
the dilation Dis defined by D:= maxiDi. It holds that Dis a lower bound for
the length of an optimal schedule.
Since there are algorithms known to determine paths for routing the packets
(see [24, 16] or simply take shortest paths) we will also consider the packet routing
problem with fixed paths. An instance of this problem is a tupel (G, M,P)such
that Gis a (directed or undirected) graph, Mis a set of packets and Pis a set
of predefined paths. Since the paths of the packets are given in advance they do
not need to be computed here. The aim is to find a schedule with the properties
described above such that the makespan is minimized. For each packet Miwe
define Dito be the length of the path Pi, again assuming that all edges have unit
length. Like above we define the dilation Dby D:= maxiDi. For each edge ewe
define Ceto be the number of paths that use e. Then we define the congestion C
by C:= maxeCe. It holds that Cand Dare lower bounds for the length of an
optimal schedule.
1.2. Related Work. Packet routing and related problems have been widely stud-
ied in the literature. Di Ianni showed that the delay routing problem [15] is NP-
hard. The proof implies that the packet routing problem is NP-hard as well. Leung
et al. [19, chapter 37] studied packet routing on different graph classes, including
in- and out-trees. In particular, they showed that for those trees the farthest-
destination-first (FDF)-algorithm works optimally. In [3] Busch et al. studied the
direct routing problem, that is the problem of finding a routing schedule such that
a packet is never delayed once it has left its start vertex. They gave complexity
results and algorithms for finding direct schedules.
Mansour and Patt-Shamir [20] studied greedy scheduling algorithms (algorithms
that always forward a packet if they can) in the setting where the paths of all packets
are shortest paths. They proved that in this setting every packet Mireaches its
destination after at most Di+N−1steps where Diis the length of the path of
Miand Nis the number of packets in the network. Thus, giving priority to the
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 3
packets according to the lengths of their paths yields an optimal algorithm if we
assume that the path-lengths are pairwise different.
In [17] Leighton et al. showed that there is always a routing schedule that
finishes in O(C+D)steps. In [18] Leighton et al. presented an algorithm that
finds such a schedule in polynomial time. However, this algorithm is not suitable
for practical applications since the hidden constants are very large. There are
also some local algorithms for this problem, needing O(C) +(log∗N)O(log∗N)D+
poly (log N)6[23] and O¡C+D+ log1+²N¢[21] steps with high probability (recall
that Ndenotes the number of packets in the network). For the case that all paths
are shortest paths, Meyer auf der Heide et al. [2] presented a randomized online
routing protocol which needs only O(C+D+ log N)steps with high probability.
Using the algorithm by Leighton et. al as a subroutine Srinivasan and Teo [24]
presented an algorithm that solves the packet routing problem with variable paths
with a constant approximation factor. This algorithm was recently improved by
Koch et al. [16] for the more general message routing problem (where each message
consists of several packets).
The packet routing problem is closely related to the multi-commodity flow over
time problem [12, 7, 8, 13, 14]. In particular, Hall et al. [12] showed that this
problem is NP-hard, even in the very restricted case of series-parallel networks. We
obtain the the packet routing problem with variable paths if we additionally require
unit edge capacities, unit transit times, and integral flow values. If there is only one
start and one destination vertex then the packet routing problem is equivalent to
the quickest flow problem. It can be solved optimally in polynomial time, e.g., using
the Ford-Fulkerson algorithm for the maximum flow over time problem [5, 9, 10]
together with a binary search framework.
Adler et al. [1] studied the problem of scheduling as many packets as possi-
ble through a given network in a certain time frame. They gave approximation
algorithms and NP-hardness results.
1.3. Our Contributions. We show that the special case of the packet routing
problem is NP-hard to approximate with a factor of 6/5−²for ² > 0. For the
packet routing problem restricted to planar graphs and directed trees we show that
it is also NP-hard to approximate within factors 7/6−²and 8/7−², respectively.
These results hold no matter if the paths of the packets are variable or given in
advance. All results hold on directed and undirected graphs. We also show that
it is NP-hard to approximate the packet routing problem with fixed paths with an
absolute error of kfor any k≥0.
For the packet routing problem on directed trees, we show that the FDF-algorithm
can perform arbitrarily bad: the obtained schedule can be longer by an arbitrarily
large factor than the optimal schedule. However, we give a factor 2-approximation
algorithm for undirected trees that uses the FDF-algorithm as a subroutine. For
directed trees, we show how to solve the path coloring problem optimally. Having
computed such a coloring, we show how to construct a direct schedule whose length
is bounded by C+D−1. Then we present an algorithm for directed trees which
constructs an optimal direct schedule of length Din the setting that the lengths of
the paths of the packets are pairwise different. For all our algorithms we show that
the analysis of the respective approximation ratios is tight.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 4
1.4. Outline of the paper. In Section 2 we present our complexity results for
the packet routing problem on different graph classes. In Section 3 we present
algorithms for the packet routing problem on different graph classes. Finally in
Section 4 we summarize our results.
2. Complexity results
In this section we show the NP-hardness of the packet routing problem on several
graph classes. For some settings we can also prove that it is NP-hard to approximate
the problem within certain approximation factors. We distinguish between fixed
and variable paths.
2.1. General Graphs. We study the complexity of the packet routing problem
without imposing any conditions on the graphs.
Theorem 1. It is NP-hard to approximate the packet routing problem with fixed
paths with an approximation factor of 6/5−²for all ² > 0.
Proof. In this proof we employ a technique which was used in [25] for showing
that the general acyclic job shop problem is NP-hard to approximate within an
approximation factor better than 5/4. We reduce from 3-BOUNDED-3-SAT. In
this problem we are given a 3-SAT formula in which each variable occurs at most
three times. The question is whether there is an assignment for the variables such
that the formula is satisfied. It was shown in [11] that 3-BOUNDED-3-SAT is NP-
hard. We assume that we are given a 3-BOUNDED-3-SAT formula with a set of
clauses {C1, C2, ..., Cm}. We construct an instance of the packet routing problem
corresponding to this formula. We will show that the formula is satisfiable if and
only if the length of an optimal schedule is at most 5.
W.l.o.g. we assume that each variable occurs at most two times as a positive
literal and at most two times as a negative literal in the formula. If a variable
occurs three times positive then we just set it true and thus satisfy all the clauses
containing this formula. If the variable occurs three times negative then we set the
variable false. We also assume that each clause contains two or three variables.
In the sequel we will explain how we construct our graph and the packets with
their start and destination vertices from this formula. Figure 2.1 shows a part of
our construction for the formula (x∨y∨z). For each variable xwe introduce the
vertices vx,1, vx,2, ..., vx,11. For each clause Cthere is a vertex vCand a vertex
v0
C. If Ccontains only two variables there is an additional vertex v00
C. We add
all the edges to the graph which are necessary for the packets according to their
predefinded paths (we define the paths below).
Now we introduce the packets. For each variable xwe have four packets labeled
x1,¯x1, x2,¯x2. We will call them the variable packets later on. These packets encode
whether xis set to true or false in the variable assignment which corresponds to the
schedule. The intuition is that a variable xis set to true if x1and x2are schedules
at time t= 0 and ¯x1and ¯x2are schedules at time t= 1. If ¯x1and ¯x2are schedules
at time t= 0 and x1and x2are scheduled at time t= 1 then xis set to false.
The predefined paths for the variable packets ensure that other schedules for the
variable packets would cause the overall schedule to be longer than 5. For each
occurence of the variable xin a clause we have a packet. We denote by cx,i the
packet for the i-th positive occurence of the variable xand by c¯x,i the packet for
the i-th negative occurence of the variable x. We will call those packets the clause
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 5
Packet Path
Packets for variables x
x1vx,1, vx,3, vx,5, vx,7, vx,10 For each variable x
x2vx,2, vx,4, vx,5, vx,6, vx,8For each variable x
¯x1vx,1, vx,3, vx,5, vx,6, vx,9For each variable x
¯x2vx,2, vx,4, vx,5, vx,7, vx,11 For each variable x
Packets for clauses Cwith three variables
cx,1vC, v0
C, vx,7, vx,10 where Ccontains the first positive occurence of x
cx,2vC, v0
C, vx,6, vx,8where Ccontains the second positive occurence of x
c¯x,1vC, v0
C, vx,6, vx,9where Ccontains the first negative occurence of x
c¯x,2vC, v0
C, vx,7, vx,11 where Ccontains the second negative occurence of x
Packets for clauses Cwith two variables
cx,1vC, v0
C, v00
C, vx,7, vx,10 where Ccontains the first positive occurence of x
cx,2vC, v0
C, v00
C, vx,6, vx,8where Ccontains the second positive occurence of x
c¯x,1vC, v0
C, v00
C, vx,6, vx,9where Ccontains the first negative occurence of x
c¯x,2vC, v0
C, v00
C, vx,7, vx,11 where Ccontains the second negative occurence of x
Table 1. The predefined paths of the packets.
packets. In a satisfying variable assignment there must be at least one variable x
(or ¯xrespectively) in each clause Cwhich satisfies C. The intuition is that the
packet cx,j (or c¯x,j respectively) corresponding to this variable x(or ¯xrespectively)
is scheduled last (at time t= 2). In Table 1 we define the predefined paths of the
packets.
Now we want to prove that the length of an optimal schedule is at most 5 if and
only if the formula is satisfiable. For the first part we assume that our formula is
satisfiable. We consider a variable assignment such that the formula is satisfied.
We construct a schedule as follows. For each variable xwhich is set true in the
satisfying variable assignment we schedule the packets x1and x2at time 0and the
packets ¯x1and ¯x2are scheduled at time 1. For each false variable ywe schedule
the packets y1and y2at time 1and the packets ¯y1and ¯y2at time 0. Since our
assignment of the variables satisfies the formula, for each clause Cthere has to be
one literal xwhich satisfies the clause. We schedule the packets corresponding to
the literals in Cin such a way that the packet corresponding to the literal xleaves
vCat time t= 2. We schedule the two other packets of Cin an arbitrary order at
times t= 0 and t= 1.
Occuring collisions (i.e., situations where two or more packets need to use the
same edge at a time) are resolved arbitrarily. We want to show that the length of
this schedule is 5. Let xibe a variable packet which leaves its start vertex at time
t= 0. It can be delayed at most once in our schedule, namely by a clause packet
which leaves its start vertex at time t= 1. Thus xireaches its destination vertex
after at most 5 timesteps. Now let xibe a variable packet which left its start vertex
at time t= 1. This implies that xwas set to false in the variable assignment.
Thus, there can be no clause packet cx,i which left its start vertex at time t= 2.
Therefore, xiwill not be delayed on its way and will reach its destination vertex after
5 timesteps. For “negative” variable packets ¯xiwe can apply the same reasoning.
Now let cx,i be a clause packet of a clause with three literals. If cx,i was scheduled
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 6
cx,1
¯x2
x2
¯x1
x1
x2
¯x2
¯x1
x1
cx,1
v0
C
vx,1
vx,2
vC
vx,3
vx,4
vx,5
vx,6
vx,7
vx,8
vx,9
vx,10
vx,11
Figure 2.1. A part of the graph for the clause (x∨y∨z). The
different lines represent the ways of the packets through the net-
work. The parts corresponding to the variables yand zand their
packets are omitted for brevity.
at time t= 0 it will not be delayed at all and will reach its destination after 3
timesteps. If cx,i was scheduled at time t= 1 it can be delayed by at most one
variable packet (by at most one timestep) and will therefore reach its destination
after at most 5 timesteps. Finally, if cx,i was scheduled at time t= 2 we know
that xwas set true in the variable assignment. This implies that the packets x1
and x2were scheduled at time t= 0 and will not be able to delay cx,i. Thus, cx,i
will reach its destination vertex at time t= 5. We can apply the same reasoning to
clause packets c¯x,i for negated literals. For clause packets corresponding to clauses
with only two literals we can apply a similar reasoning: The two packets behave
like the last two packets which are scheduled in a vertex vCwhere Cis a clause
with three literals.
Now we assume that there is a schedule of length 5 or less. We want to show
that the formula is satisfiable. In order to do this, we show how we can construct
a satisfying variable assignment from the schedule. W.l.o.g. we assume that the
schedule never delays a packet if it is the only packet that wants to use an edge at a
time. Consider a variable xand its packets x1, x2,¯x1, and ¯x2. Since x1and ¯x1have
the same start vertex, either x1is scheduled at time 0 and ¯x1is scheduled at time
1 or vice versa. The same holds for x2and ¯x2. Since the length of the schedule is
5, we see that those of the packets which are scheduled at time 1 are not delayed
later in the schedule. From this it follows that x1and x2are scheduled at the same
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 7
time. If they are scheduled at time 0 we set the variable xto true, otherwise we
set xto false. We do this with all variables. Now we want to show that this leads
to a satisfying assignment for the formula.
Let Cbe a clause. We discuss the case where Ccontains only positive literals.
The other cases can be proven similarly. Let C= (x∨y∨z). Consider the three
packets cx,i,cy,j,cz,k for C. They all originate at the same vertex vC. We consider
the packet of the three which was scheduled last (i.e., at time t= 2). W.l.o.g.
let cx,i be this packet. Since the length of our schedule is 5 we conclude that cx,i
was never delayed after time t= 2. Thus, the packet ximust have been scheduled
at time t= 0. Otherwise both xiand cx,i would reach the vertex vx,6(or vx,7
respectively) at time t= 4 and the total makespan of the schedule would be 6.
This is a contradiction.
This implies that we set the variable xto true in our variable assignment. There-
fore, the clause Cis satisfied. Doing this reasoning for all clauses shows that the
formula is satisfied. ¤
As corollaries we obtain the following results for the packet routing problem with
fixed paths on directed graphs and for the packet routing problem with variable
paths.
Corollary 2. It is NP-hard to approximate the packet routing problem with fixed
paths on directed graphs with an approximation factor of 6/5−²for all ² > 0.
Proof. It is straight forward to see that we can orientate the edges of the underlying
graph in the construction of Theorem 1 such that the packets always move in the
direction of the edges (see Figure 2.2).
¤
Corollary 3. It is NP-hard to approximate the packet routing problem with variable
paths on directed graphs within an approximation factor of 6/5−²for all ² > 0.
Proof. Consider the construction used in Theorem 1. It turns out that if the graph
is directed the path for each packet is unique. Therefore, allowing the packets to
choose their paths does not change anything.
Now we show that all paths are unique. Let xbe a variable. We orientate
the edges in the direction in which the packets move. See Figure 2.2 for a sketch.
Denote by Gxthe subgraph induced by the vertices vx,1, ..., vx,11. There are no
edges oriented out of Gx. Since Gxis a tree, it holds that once a packet has
reached Gxthe remainder of its path is unique. So the path of each variable packet
is unique. Now let Cbe a clause and let pCbe a clause packet corresponding to C.
In the schedule the packet pCpasses the vertices vC,v0
C(and v00
Cif Ccontains
only two variables). After this pChas to move to a vertex vyin a subgraph Gy
of a variable y. Since there is no directed way out of Gyand there is exactly one
variable ysuch that the destination vertex of pCis contained in Gythe path of of
pCis unique. Therefore, the paths of all clause packets are unique. ¤
Corollary 4. It is NP-hard to approximate the packet routing problem with variable
paths on undirected graphs with an approximation factor of 6/5−²for all ² > 0.
Proof. It turns out that in the construction of Theorem 1 the packets cannot take
advantage of being allowed to use paths different than the ones specified in the
reduction.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 8
cx,1
¯x1
x2
x1
x1
¯x1
¯x2
x2
cx,1
v0
C
vx,1
vx,2
vC
vx,3
vx,4
vx,5
vx,6
vx,7
vx,8
vx,9
vx,10
vx,11
¯x2
Figure 2.2. A part of the directed graph for the clause (x∨y∨z).
We use the same reduction as defined in Theorem 1. For each packet we set
its start vertex and destination vertex as defined in Table 1. Since we study the
packet routing problem with variable paths the latter can be chosen arbitrarily by
the schedule. We want to prove that the formula is satisfiable if and only if the
optimal schedule has length 5. Assume that the formula is satisfiable. In the proof
of Theorem 1 it was shown that there exists a schedule of length 5 which uses the
paths specified in Table 1. Now assume that there is a schedule of length 5. For
all variable packets and all clause packets it holds that all paths to their respective
destination vertices different from the ones defined in Table 1 need more than 5
edges. Therefore, the packets have to move according to the paths defined in the
table. The remainder of the proof is exactly as in Theorem 1. ¤
If there is only one start and one destination vertex and the paths of the packets
are variable, the packet routing problem is solvable in polynomial time, e.g., using
the Ford-Fulkerson algorithm for the maximum flow over time problem [5, 9, 10]
together with a binary search framework. However, if the paths of the packets are
fixed the problem becomes NP-hard.
Corollary 5. It is NP-hard to approximate the packet routing problem with fixed
paths on directed or undirected graphs with one start or one destination with an
approximation factor of 7/6−²for all ² > 0. If there is a single start and a
single destination vertex it is NP-hard to approximate the problem within a factor
of 8/7−²for all ² > 0.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 9
Proof. We take the construction of Theorem 1 and add a super start-vertex vs.
We connect vswith each start vertex vof the graph (one edge per packet that
starts in v). For each packet we set vsto be its start vertex and define the rest
of its path according to Table 1. Thus, the lengths of all paths are increased
by one. This proves the first claim. We can do the same for the case of only
one destination vertex by introducing a super-destination vertex and obtain the
same hardness result for this setting. Doing both (adding a super-start vertex and
a super-destination vertex) shows that it is NP-hard to approximate the packet
routing problem with fixed paths on undirected graphs with one start and one
destination vertex with a factor of 8/7−²for all ² > 0. In all these constructions
we can orientate the edges such that all the packets always move in the direction
of the edges (see also Corollary 2). ¤
2.2. Planar Graphs. The part of the graph shown in Figure 2.2 is in fact a tree.
However, the whole construction is in general not even planar. E.g., consider the
formula (x∨y∨z)∧(x∨¯y∨z)∧(x∨y∨¯z). Figure 2.3 shows a sketch of the
graph constructed according to the construction in Theorem 1. We want to show
that it contains a K3,3-minor which implies that it is not planar. We define A:=
{v0
1, v0
2, v0
3}and let B:= {vx,6, vy,7, vz,6}. We can see that there are edge-disjoint
paths between all pairs of vertices (va, vb)with va∈Aand vb∈B. Therefore, the
graph contains a K3,3-minor and is not planar.
Even though the construction in Theorem 1 is not planar, it can be easily ad-
justed to obtain a planar graph. However, this is to the cost of a slightly worse
bound for the approximation ratio.
Theorem 6. On planar graphs it is NP-hard to approximate the packet routing
problem with fixed paths with an approximation factor of 7/6−²for any ² > 0.
Proof. We change the construction used in Theorem 1 slightly in order to obtain
a planar graph. We introduce the vertices vL(Lfor Left) and vR(Rfor right).
We change the predefined paths of the packets such that all packets pass either vL
or vR. This extends the lengths of the path by one edge in comparison with the
construction in Theorem 1. Figure 2.4 shows a sketch of this construction.
Now we describe the construction in detail. In addition to the vertices defined
in the proof of Theorem 1 we introduce the vertices vL,vRand vertices v0
1,x and
v0
2,x for each variable x. The predefined paths of the packets are shown in Table 2.
From the sketch in Figure 2.4 it is easy to see that the graph is planar.
Similar to Theorem 1 it holds that the length of an optimal schedule for this
network is 6 if and only if the formula is satisfiable. The proof works along the
lines of the proof of Theorem 1. Assume that the formula is satisfiable. We schedule
the packets with the same technique as in the proof of Theorem 1. However, here
we must be more careful with the schedule of the packets of a clause Cwhich
are not needed in order to satisfy C. There might be a variable xsuch that two
of those packets want to use the edge {vL, vx,6}or {vR, vx,7}at time t= 3 (this
happens when both packets startet at time t= 1). We show that there is always
a schedule in which this does not happen. We consider a graph G0= (V0, E0).
The set V0contains one vertex for each literal in a clause which is not needed in
order to satisfy its respective clause. Two vertices are connected if and only if
their respective literals they are in the same clause or the paths of their respective
packets share an edge. Note that this implies that the degree of a vertex is at most
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 10
v0
1
v1
vx,4
vx,3
vx,1
vx,5
vx,9
vx,11
vx,10
vx,8
vx,2
vx,7
vx,6
vy,1vy,2
vy,4
vy,3
vy,5
vy,8vy,11
vy,10
vy,9
vy,7
vy,6
vz,1vz,2
vz,3vz,4
vz,5
vz,8
vz,10
vz,11
vz,9
vz,6vz,7
v0
3
v3
v0
2
v2
Figure 2.3. In general the graphs constructed in the proof of
Theorem 1. The gray and black vertices form the sets Aand Bfor
the K3,3-minor.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 11
...
...
v0
C1
vC1
vx,1
vx,5
vx,9
vx,11
vx,10
vx,8
vx,2
vx,3vx,4
v0
x,1v0
x,2
vx,7
vx,6
v0
C2
vC2
vCk
v0
Ck
vLvR
Figure 2.4. Sketch of a planar embedding of the construction in
Theorem 6.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 12
Packet Path
Packets for variablex x
x1vx,1, v0
x,1, vx,3, vx,5, vx,7, vx,10 For each variable x
x2vx,2, v0
x,2, vx,4, vx,5, vx,6, vx,8For each variable x
¯x1vx,1, v0
x,1, vx,3, vx,5, vx,6, vx,9For each variable x
¯x2vx,2, v0
x,2, vx,4, vx,5, vx,7, vx,11 For each variable x
Packets for clauses Cwith three variables
cx,1vC, v0
C, vL, vx,7, vx,10 where Ccontains the first positive occurence of x
cx,2vC, v0
C, vR, vx,6, vx,8where Ccontains the second positive occurence of x
c¯x,1vC, v0
C, vR, vx,6, vx,9where Ccontains the first negative occurence of x
c¯x,2vC, v0
C, vL, vx,7, vx,11 where Ccontains the second negative occurence of x
Packets for clauses Cwith two variables
cx,1vC, v0
C, v, vL, vx,7, vx,11 where Ccontains the first positive occurence of x
cx,2vC, v0
C, v00
C, vR, vx,6, vx,11 where Ccontains the second positive occurence of x
c¯x,1vC, v0
C, v00
C, vR, vx,6, vx,11 where Ccontains the first negative occurence of x
c¯x,2vC, v0
C, v00
C, vL, vx,7, vx,11 where Ccontains the second negative occurence of x
Table 2. The predefined paths of the packets.
two. Let V00 ⊆V0be the set of vertices corresponding to packets in clauses with
only two literals. It holds that the degree of vertices in V00 is at most one.
We want to show that G0is bipartite. Let cbe a cycle in G0. Since the degree of
each vertex in G0is at most two the cycle cmust be a connected component of G0.
Moreover, it cannot contain vertices in V00. For each clause Cwhich contributes
vertices to cboth vertices must be in c. This implies that cis has even length
and thus G0is bipartite. Therefore, we can color its vertices with two colors, say 0
and 1. Then we schedule the corresponding packets according to the color of the
vertices at times t= 0 and t= 1. This ensures that there is no collision of two
packets when using edges {vL, vx,6}or {vR, vx,7}for a variable x. Thus, we can
guarantee that the length of the overall schedule is at most 6.
The proof for constructing a satisfying variable assignment out of a schedule of
length 6 works exactly as in the proof of Theorem 1. ¤
Corollary 7. On undirected planar graphs it is NP-hard to approximate the packet
routing problem with variable paths with an approximation factor of 7/6−²for any
² > 0.
Proof. Like in Corollary 4 it turns out that the packets cannot take advantage of
being able to choose a path different from the one predefined in Table 2. This can
be proven similarly as in the proof of Corollary 4. ¤
2.3. Trees. We can show that the packet routing problem is still NP-hard to ap-
proximate if we restrict the considered graphs to directed trees.
Theorem 8. It is NP-hard to approximate the packet routing problem on directed
trees with an approximation ratio of 8/7−²for any ² > 0.
Proof. We reduce from 3-BOUNDED-3-SAT. Our construction is a slightly changed
version of the construction in Theorem 1. Since the graph is a tree the bound on
the approximation ratio that we can prove is slightly worse.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 13
x2
¯x2
cx,1
¯x1
x1
¯x1
x1
cx,1
¯x2
x2
vx,1
vx,2
vC
vr
vx,6
vx,3
[1,4]
[1,4]
[2,3]
vx,4
[5,6]
[5,6]
[5,6]
vx,8
vx,7
vx,5
[5,6]
Figure 2.5. A part of the graph for the clause C= (x∨y∨z)
(construction for Theorem 8). The parts corresponding to the
variables yand zand their packets are omitted for brevity. The
time intervals at the edges denote the time when the respective
edge is blocked. Note that the first timestep is t= 0.
Packet Path
Variable packets for variable x
x1vx,1, vr, vx,3, vx,4For each variable x
x2vx,2, vr, vx,6, vx,8For each variable x
¯x1vx,1, vr, vx,6, vx,7For each variable x
¯x2vx,2, vr, vx,3, vx,5For each variable x
Clause packets for clause C
cx,1vC, vr, vx,3, vx,4where Ccontains the first positive occurence of x
cx,2vC, vr, vx,6, vx,8where Ccontains the second positive occurence of x
c¯x,1vC, vr, vx,6, vx,7where Ccontains the first negative occurence of x
c¯x,2vC, vr, vx,3, vx,5where Ccontains the second negative occurence of x
Table 3. The predefined paths of the packets.
Assume we are given a 3-BOUNDED-3-SAT formula φ. We construct an instance
of the packet routing problem with fixed paths such that the underlying graph is a
directed tree. In particular, the packets always move in the direction of the edges.
We show that the formula is satisfiable if and only if the optimal schedule has
length 7. Like in the proof of Theorem 1, we assume that each clause contains at
least two variables and that each variable occurs at most two times positive and at
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 14
most two times negated in φ. The construction is sketched in Figure 2.5. The main
difference in comparison with Theorem 1 is that now there is a central vertex vr
that all packets pass. For each variable xin the formula, there are the four variable
packets x1,x2,¯x1and ¯x2. They can be scheduled at time t= 0 or t= 4. The
intuition is that if x1and x2are scheduled at time t= 0 then we set the variable x
true, if x1and x2are scheduled at time t= 4 then we set the variable xfalse.
Note that now it could happen that this assignment is not well-defined, i.e., the
packets x1and ¯x2go first or the packets x2and ¯x1go first. Like in the proof of
Theorem 1 our construction ensures that this leads to a schedule which is strictly
longer than 7 timesteps. Moreover, for each literal in a clause Cthere is one packet.
Packets corresponding to literals in the same clause share the first edge on their
path. Given a satisfying variable assignment for φthere is at least one literal in C
which satisfies the clause. The packet which corresponds to this literal is scheduled
last.
Now we describe the construction in detail. For each variable xwe introduce
vertices vx,1, vx,2, ..., vx,8. We also introduce the four variable packets x1,x2,¯x1,
and ¯x2. In the formula, we fix an order of the clauses. For each clause Cthere
is a vertex vC. For each literal in Cthere is one clause packet. We write cx,i for
the packet corresponding to the i-th positive occurence of xand c¯x,i for the packet
corresponding to the i-th negative occurence of x. The predefined paths for the
packets are shown in Table 3 and sketched in Figure 2.5. Note that the underlying
graph is a directed tree.
In order to make the construction work as desired we want to block some edges
at certain times. This can be done by introducing blocking packets. If we want to
block an edge eat time t=¯
twe introduce a blocking packet be,¯
twhich needs to
use eat time t=¯
tor otherwise would not reach its destination before time t= 7.
Note that this does not destroy the tree structure of the underlying graph. In order
to clearify matters we do not explicitely define the paths of the blocking packets.
Instead, we state which edges are blocked at what time. Let xbe a variable. The
edges (vx,1, vr)and (vx,2, vr)are blocked during the time interval [1,4] (note that
t= 0 is the first timestep). The edges (vx,3, vx,4),(vx,3, vx,5),(vx,6, vx,7), and
(vx,6, vx,8)are blocked during the time interval [5,6]. For each clause Cwith three
literals the edge (vC, vr)is blocked during the time interval [2,3]. For each clause
C0with two literals the edge (vC0, vr)is blocked during the time interval [1,3].
Now we want to prove that φis satisfiable if and only if the optimal schedule
has length 7. First assume that φis satisfiable. We consider a variable assignment
that satisfies the formula and schedule the packets as follows: Everytime there is a
packet Mthat is the only packet that needs to use the next edge on its path we
move M. Let xbe a variable. If xis set true in our variable assignment then we
schedule the packets x1and x2at time t= 0 and the packets ¯x1and ¯x2at time
t= 4. If xis set false then we schedule x1and x2at time t= 4 and ¯x1and ¯x2at
time t= 0.
Since our variable assignment satisfies the formula in each clause Cthere must
be at least one literal y(or ¯yrespectively) which satisfies the clause. We schedule
the packet corresponding to y(or ¯yrespectively) to leave vCat time t= 3. We
schedule the other two packets to leave vCin arbitrary order at times t= 0 and
t= 1 (if Ccontains only two literals the other packet is scheduled at time t= 0).
Blocking packets are never delayed by other packets. If there is a variable packet
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 15
and a clause packet competing for using an edge at the same time we give priority
to the variable packet (this is only for simplification of the proof). Other ties are
broken arbitrarily.
Now we show that all packets arrive at their destination vertices after at most 7
timesteps. First assume that x1started at time t= 0. Since the edge (vx,2, vr)is
blocked during the time interval [1,4] the packet ¯x2cannot reach vrbefore t= 5.
Thus, x1reaches vx,6at time t= 2 and vx,8at time t= 3. For the case that the
packets x2,¯x1, or ¯x2startet at time t= 0 the proof works similarly.
Now assume that ¯x2startet at time t= 4. The reasoning above shows that ¯x2
cannot collide with x1. Since variable packets have a higher priority than clause
packets we conclude that ¯x2reaches vx,6at time t= 6 and vx,8at time t= 7.
For the case that the packets x1,x2, or ¯x1startet at time t= 4 the proof works
similarly.
Next we discuss the clause packets. First assume that the packet cx,1was sched-
uled at time t= 0 or t= 1. In both cases it reaches vx,6at time t= 4 at the latest
and vx,8at time t= 5 at the latest. (Note that either the packet x1or the packet
¯x2uses the edge (vr, vx,6)at time t= 1 and thus it does not make a difference for
our reasoning if cx,1was scheduled at time t= 0 or t= 1). For the other clause
packets which were scheduled at time t= 0 or t= 1 the proofs works similarly.
Now assume that the clause packet c¯x,2was scheduled at time t= 3. This implies
that in the satisfying variable assignment xwas set false. Then c¯x,2reaches vrat
time t= 4. From the above reasoning it follows that it cannot collide with any other
packet at vr. Moreover, it reaches vx,6at time t= 5. The edge (vx,6, vx,8)is blocked
in the time interval [5,6]. The packet ¯x2is the only packet that c¯x,2competes with
for using the edge (vx,6, vx,8). But since xwas set false in our variable assignment
¯x2startet at time t= 0 and the above reasoning shows that ¯x2reached vx,8at time
t= 3. Thus, c¯x,2reaches vx,8at time t= 7. This shows that all packets reach their
respective destination vertices after at most 7 timesteps.
Now assume that there is a schedule Sof length 7. We want to show that there
is a variable assignment which satisfies φ. Let xbe a variable. If the packets x1
and x2were both scheduled at time t= 0 then we set xto true, if the packet ¯x1
and ¯x2were both scheduled at time t= 0 we set xto false. We will show in the
sequel that this assignment is well-defined and that it satisfies φ. First we show
that in Seither x1and x2were both scheduled at time t= 0 or ¯x1and ¯x2were both
scheduled at time t= 0. Assume on the contrary that x1and ¯x2were scheduled at
time t= 0. Since the edges (vx,1, vr)and (vx,2, vr)are blocked in the time interval
[1,4] and Shas length 7 this implies that ¯x1and x2were scheduled at time t= 4.
However, this implies that both packets arrive at vrat time t= 5. Since both need
to use the edge (vr, vx,3)next this contradicts that Shas length 7. The case that
¯x1and x2were scheduled at time t= 0 can be proven similarly. Now we prove
that our variable assignment satisfies φ. Consider a clause Cwith three literals
(the case that Ccontains only two literals can be proven similarly). Since the edge
(vC, vr)is blocked during the time interval [2,3] there must be at least one packet
corresponding to Cwhich was scheduled at time t= 3 or later. Let cx,1be this
packet (the cases for the other packets can be proven similarly). We want to show
that the packet x1was scheduled at time t= 0 and thus xis set true in our variable
assignment. Assume on the contrary that x1was scheduled at time t= 4 or later.
Then it can arrive at vx,6at time t= 6 the earliest. Since cx,1was scheduled at
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 16
time t= 3 it can arrive at the vertex vx,6at time t= 5 the earliest. The edge
(vx,6, vx,8)is blocked in the time interval [5,6] and thus cx,1cannot have reached
vx,8by time t= 6. Thus, in order to reach vx,8at time t= 7 the packets cx,1and
x1must use the edge (vx,6, vx,8)at time t= 6. This is a contradiction. Thus, x1
was scheduled at time t= 0 and we set xtrue. Doing this reasoning for all clauses
Cshows that our variable assignment satisfies φ.¤
Note that the above result implies that it is also NP-hard to approximate the
packet routing problem on undirected trees with a performance ratio of 8/7−²for
all ² > 0.
2.4. Absolute approximation. All NP-hardness results that we presented so far
constructed reductions with a gap of one time unit between yes- and no-instances of
3-BOUNDED-3-SAT. This raises the question whether it is NP-hard to approximate
the packet routing problem with an absolute error. We answer this question in the
affirmative.
Theorem 9. It is NP-hard to approximate the packet routing problem with fixed
paths on directed planar graphs with an absolut error of k.
Proof. We give a reduction from 3-BOUNDED-3-SAT. Let φbe a 3-BOUNDED-
3-SAT formula. We show by induction that for each kthere is an integer αkand
an instance Ikof the packet routing problem with fixed paths on directed planar
graphs with the properties that
•OPT (Ik) = αkif φis satisfiable and
•OPT (Ik) = αk+k+ 1 if φis not satisfiable
In order to clearify matters, we construct Iksuch that each packet has its own start
and its own destination vertex. For I0we take the construction which was used in
the proof of Theorem 6 and introduce two additional vertices for each packet such
that the start and destination vertices are unique. This increases the makespan by
two. This implies that α0= 8. Let n0be the number of packets that are used in
this construction.
For the inductive step we assume that the claim is true for all i≤k. We want
to construct a packet routing instance Ik+1 with the above properties. A sketch of
the construction is given in Figure 2.6. Let nkbe the number of packets used in
Ik. We denote by αk+1 is the length of the optimal makespan for Ik+1 assuming
that φis satisfiable. In order to meet the properties stated above we want that an
optimal schedule needs at least αk+1 + (k+ 1) + 1 steps if φis not satisfiable.
We will use nkcopies Fiof Ikand denote them as formula gadgets. The intuition
is the following: If φis satisfiable then all packets in all formula gadgets arrive at
their destination vertices at time t=αk. If φis not satisfiable then in each gadget
there is at least one packet that reaches its destination vertex at time t=αk+k+1.
Thus, there is an absolut difference of k+ 1 between yes- and no-instances. We
want to increase this difference to k+ 2.
In case that φis not satisfiable we want to control which packet from a formula
gadget is late (i.e., reaches its destination vertex at time t=αk+k+1). In order to
achieve this we introduce another type of gadget which we call the sorting gadget.
We place one sorting gadget behind each formula gadget. A sorting gadget works
as follows:
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 17
Its input consists of all packets from a formula gadget and an additional sorting
packet. If all packets from the formula gadget left it at time t=αkthen inside the
sorting gadget no packets is delayed. If there is a non-empty set of packets Pwhich
left the formula gadget at time t=αk+k+ 1 then in the sorting gadget either one
packet in Pis delayed once or the sorting packet is delayed once. If a packet in P
is delayed inside the sorting gadget then we can already guarantee that the overall
makespan has to be at least αk+1 +k+ 2. So for the remainder of the proof we
assume that if φis not satisfiable it will be the sorting packet that will be delayed
inside the sorting gadget.
Finally we place an additional copy ¯
Fof Ik. We will call this the final gadget.
The input of the final gadget consists of all sorting packets. The intuition is that if φ
is satisfiable no sorting packet will be delayed inside the sorting gadgets. Moreover,
all sorting packets will need only αkadditional steps inside the final gadget.
If φis not satisfiable each sorting packet will be delayed once in the sorting
gadget and one of them will need αk+k+ 1 steps inside the final gadget. This
causes an absolute difference of k+ 2 between yes- and no-instances.
Now we describe the construction in detail. Let F1, ..., Fnkbe the nkcopies of
Ik(the formula gadgets). We know that φis satisfiable if and only if in an optimal
schedule all packets leave the formula gadgets after at most αktimesteps. We call
the packets used in formula gadgets the formula packets.
For a formula packet mjdenote by sjits start vertex and by ujits first vertex be-
hind in the formula gadget (i.e., the first vertex outside the gadget), see Figure 2.6.
Behind each formula gadget Fjwe place a sorting gadget Sj. The input of the
sorting gadget Sjconsists of all packets leaving Fjand an additional sorting packet
qj. Figure 2.7 depicts a sketch of a sorting gadget. For a packet pjdenote by wj
the first vertex outside of the sorting gadget. Inside the sorting gadget the formula
packets move on horizontal lines consisting of 2nkvertices without interfering with
each other. The sorting packet first moves αk+k+4 edges (this can be understood
as an artifical delay). Then it intersects the paths of each formula packet in one
edge. After having left the sorting gadget the formula packets move on a path of
additional αk+k+ 4 vertices (there is one path for each packet, so the packets do
not interfere with each other). The paths of the sorting packets are then connected
to the final gadget ¯
Fwhich is another copy of Ik. The entire construction is shown
in Figure 2.6. We set αk+1 := 2nk+ 2 ·αk+k+ 2.
Now we want to prove that if φis satisfiable then there is a schedule whose length
is at most αk+1. We construct a schedule with that length. In this schedule we
never delay a packet if not necessary, i.e., if it is the only packet that needs to use
its next edge. Since φis satisfiable there is a schedule such that after αktimesteps
all formula packets pjhave reached their respective vertex uj. Inside the sorting
gadgets no packet encounters any delay. Therefore, the sorting packet reaches its
vertex wjafter (αk+k+ 2) + (2nk+ 1) = 2nk+αk+k+ 3 time steps. After
another timestep it reaches its last vertex before entering ¯
F. Since φis satisfiable
there is a schedule such that after another αktimesteps, the sorting packet reaches
its destination vertex. Thus, after 2nk+ 2αk+k+ 4 = αk+1 timesteps all sorting
packets have reached their destination vertices. A formula packet pjreaches wj
after αk+2nksteps. Since after this it has to move another αk+k+ 4 edges pjhas
reaches its destination vertex tjafter at most 2nk+2·αk+k+ 2 = αk+1 timesteps.
Thus, the length of the overall makespan is at most αk+1.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 18
...
... ... ...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
{
{
p1
p2
pnk
p3F1S1
sjujwj
pnk+1
p2nk
pnk+2
pnk+3 F2S2
pn2
k
pn2
k−nk+1
pn2
k−nk+2
pn2
k−nk+3 FnkSnk
¯
F
vj
tj
αk+k+ 2
αk+k+ 4
Figure 2.6. Construction for Theorem 9
Next we want to show that if φis not satisfiable then the optimal makespan
is at least αk+1 +k+ 2. If φis not satisfiable, then in each copy Fjthere is at
least one formula packet pjwhich reaches the vertex ujafter at least αk+k+ 1
steps. Now consider the sorting gadget Sj. By construction inside Sjeither the
sorting packet qjor pjis delayed. If pjis delayed then it needs at least another
(2nk+ 1) + αk+k+ 4 steps to reach its destination after having reached uj. This
gives 2αk+ 2nk+ 2k+ 6 = αk+1 +k+ 2 steps in total. So now assume that in each
formula gadget Fjthe the sorting packet qjis delayed . This implies that qjreaches
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 19
Sk
ujwjuj
...
wj
...
...
...
...
Figure 2.7. Sorting gadget
wjafter at least (αk+k+ 2)+(2nk+ 1)+1 steps. Then qjneeds an additional step
in order to reach their respective vertex vj. This reasoning applies to all sorting
packets qj. Since φis not satisfiable there must be at least one sorting vertex which
needs another αi+i+ 1 steps inside ¯
F. This gives 2αk+ 2nk+ 2k+ 6 = αk+k+ 2
steps in total. Thus, if φis not satisfiable, the length of an optimal schedule is at
least αk+k+ 2. The total number of packets used is (nk)2+nk=: nk+1. The
size of this construction is clearly bounded by a polynomial in the size of Ikand
therefore it is bounded by a polynomial in the size of φ.
The sketch in Figure 2.6 shows that the underlying graph for Ik+1 is planar if the
underlying graph for Ikwas planar. This proofs that it is NP-hard to approximate
the packet routing problem with fixed paths on directed planar graphs with an
absolute error of kfor any k≥0.¤
3. Algorithms
In this section we study algorithms for the packet routing problem on directed
and undirected trees.
3.1. Farthest-Destination-First-Algorithm. As a general concept we first in-
troduce the farthest destination first algorithm (FDF). Let I= (G, M,P)be an
instance of the packet routing problem with fixed paths. The FDF-algorithm com-
putes a schedule according to the following rule:
Let ebe an edge. If there is only one packet Mthat needs to use eat a time
t, we transfer Malong e. If there are several packets M1, ..., Mkwhich are ready
to use the edge eat time twe transfer the packet Mialong ewhich still has the
longest distance to go to its destination among all packet M1, ..., Mk. Ties are
broken arbitrarily. Denote by FDF(I)the longest schedule for the packet routing
instance Ithat the FDF-algorithm could possibly compute.
Let T= (V, A)be a directed tree. We call Tan out-tree if the indegree of each
vertex is at most one. We call Tan in-tree if the outdegree of each vertex is at
most one.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 20
v2
v1
G1
Figure 3.1. The graph G1
Theorem 10. On in-trees and out-trees the FDF-Algorithm works optimally.
Proof. This was shown by Leung [19]. ¤
Throughout the paper we will use the notation |S|for the length of a schedule
S. For a packet routing instance Iwith fixed or variable paths let OPT (I)denote
a schedule with minimum makespan.
In terms of approximation factor the FDF-algorithm can perform arbitrarily bad,
even if we consider only directed trees.
Theorem 11. For every k≥1there is a a directed tree Tkand a packet routing
instance Ik= (Tk,Mk)such that
|FDF (Ik)| ≥ k· |OPT (Ik)|
Proof. In order to prove the claim, we inductively construct packet routing instances
(G1,M1), ..., (Gk,Mk). Let m≥1be an integer and let i= 1. The graph G1
(see Figure 3.1) consists of two vertices {v1, v2}. The set of packets M1has m
packets which all start in v1and whose destination vertex is v2. We define all
packets to be upper packets (in the inductive step we will see the reason for this
definition). It is easy to see that for each upper packet M1there is a schedule with
total makespan m=: β1such that M1reaches its destination vertex after 1 =: α1
timesteps. Moreover, the lengths of the paths of all packets are identical. Since the
FDF-algorithm breaks ties arbitrarily, it might compute a schedule in which M1
reaches its destination v2after m=: γ1timesteps.
Now let i= 2. For J2= (G2,M2)we take mcopies of J1= (G1,M1). From
each copy J1,` we choose one packet M`and extend its path by two more vertices
{v3, v4}. We call these packets M`the upper packets and all other packets the lower
packets. For all lower packets we extend their path by two more vertices (so for
each of these packet we introduce two new vertices). The whole construction is a
directed tree and the congestion on the edge (v3, v4)is exactly m. See Figure 3.2
for a sketch of G2.
We can easily see that an optimal schedule has length 2 + m=: β2(give priority
to the upper packets and schedule the lower packets in arbitrary order). We also
see that for each upper packet M`there is an optimal schedule such that M`arrives
at its destination after 3 =: α2timesteps. Since the paths of all packets have the
same length, the FDF-algorithm schedules them in arbitrary order. In the worst
possible schedule, the upper packets are scheduled with lowest priority. For each
upper packet M`the FDF-algorithm might compute a schedule in which M`reaches
its destination after m+1+m=: γ2steps.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 21
v4
v3
...
v2,1
v1,1
v2,2
v1,2
v2,3
v1,3
v2,m
v1,m
G2
Figure 3.2. The graph G2
We continue inductively: For the construction of Jiwe take mcopies of Ji−1.
From each copy Ji−1,` we choose one upper packet M`and extend its path by the
vertices v2i−1and v2i(so all these packets now share one edge). These packets
form the upper packets of Ji. All other packets are lower packets. The paths of
all lower packets are extended by two new vertices (so we add two new vertices for
each packet). Thus, the lengths of the paths of all packets are identical (since by
the induction hypothesis they were identical in the previous iteration).
From the induction hypothesis we know that for each upper packet M`there is
a schedule for Ji−1,` of length βi−1such that M`arrives at its destination after
αi−1timesteps. Also, there is another schedule for Ji−1,` in which M`reaches
its destination after γi−1steps. Thus, for each upper packet M`in Jithere is a
schedule for Jiof length max {αi−1+1+m, βi−1+ 2}=: βiin which Mi,` reaches
its destination after αi−1+ 2 =: αisteps. Also, there is an FDF-schedule for Jiin
which M`reaches its destination after γi−1+1+m=: γisteps.
Some basic calculus shows that αi= 2i−1,βi= 2i−2 + mand γi=i·
m+i−1. Recall that F DF (Ji)is the longest possible schedule produced by the
FDF-algorithm for Ji. Then it holds that
FDF (Ji)≥γi
βi
·OPT (Ji) = i·m+i−1
m+ 2i−1·OPT (Ji)
The claim follows by choosing mand isufficiently large. ¤
3.2. Undirected Trees. Looking at Theorem 11 the FDF-algorithm does not look
very promising when good approximation factors are desired. However, we can use
it as a subroutine for computing a 2-approximation for the packet routing problem
on undirected trees. Since on trees there is a unique simple path between two
vertices, we do not distinguish between the settings with fixed and variable paths.
Instead we assume that the packets use the unique simple path between their start
and destination vertex.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 22
... ...
vMv1
v0
1
v0
2vD
v0
Dv2
Figure 3.3. Graph for showing that the analysis in Theorem 12 is tight.
The algorithm works as follows: Let Tbe a tree and let I= (T, M)be a packet
routing instance. Let vrbe an arbitrary vertex. We define vrto be the root of
the tree and orientate all edges towards vr. We observe that the orientation of the
edges splits the path of each packet Miinto two parts: in the first part Mimoves
according to the direction of the edges. In the second part of the path Mimoves
in the opposite direction of the edges. Let vibe the vertex which divides these
two parts. We split the routing problem into two subproblems: First we move each
packet Mifrom sito vi. In the second part we move each packet Mifrom vito ti.
We observe that the first part is a packet routing problem on an in-tree and can
therefore be solved optimally using the FDF-algorithm (see [19]). Similarly, the
second part is a packet routing instance on an out-tree which can also be solved
optimally using the FDF-algorithm (see [19]). In the overall schedule for I, first
we run the optimal (FDF-)schedule for the first part. Then we run the optimal
(FDF-)schedule for the second part. Denote by TREE (I)the resulting schedule
for the instance I.
Theorem 12. For the schedule TREE (I)it holds that |TREE (I)| ≤ 2·|OPT (I)|.
Proof. Since the length of an optimal schedule for each of the two subproblem
forms a lower bound for the size of an optimal schedule for the original problem,
we achieve an approximation ratio of two. ¤
Remark. It can be shown that the time needed to compute TREE (I)is bounded
by O¡n2¢. For details see [22].
Note that the runtime of O¡n2¢is optimal since the size of an optimal schedule
in the computer memory can be up to Θ¡n2¢. When implementing the algorithm
one would not let packets wait until all other packets have finished the first part
of the schedule. We would rather always move a packet when the next edge on its
path is free and prioritize the packets according to the algorithm. But even then
there is an example that shows that our analysis is tight.
Let Dbe an arbitrary positive integer (in the packet routing instance this will be
the value of the dilation). Consider the graph shown in Figure 3.3. We introduce
2·Dpackets as follows: We define M1:= (vM, vD)and M0
1:= (vM, v0
D). For
each k∈ {2, ..., D}we define Mk:= (v1, vM)and M0
k:= (v0
1, vM). The optimal
makespan for this packet routing instance is D, obtained by giving priority to the
packets M1and M0
1and scheduling the other packets in arbitrary order. In order
to analyze the schedule obtained by our algorithm we need to consider all possible
choices for vr. If vr=vMor vr=vkwith 1≤k≤Dthen the packets M0
2to
M0
khave a higher priority than M0
1and therefore M0
1will need 2·D−1steps to
reach v0
D. Analogously, if vr=v0
kwith 1≤k≤Dthen the packets M2to Mk
have a higher priority than M1and therefore M1will need 2·D−1steps to reach
v0
D. Thus, the competitive ratio of Ais at best 2·D−1
D. Since we can choose D
arbitrarily large this shows that the proven competitive ratio of 2 is tight.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 23
3.3. Directed Trees. For directed trees we obtain an even stronger result: we can
construct a direct schedule of length at most C+D−1in polynomial time. Again,
since on directed trees the paths for the packets are unique we do not distinguish
between the settings of fixed and variable paths.
The algorithm works as follows: First we find a coloring for the paths of the
packets such that two paths that share an edge have different colors. We will show
that the number of colors needed is exactly C. We assign each packet the color
of its path. Then we assign each edge a time-dependent color. The idea behind
this is that we transfer a packet Pwith color cPalong an edge e= (u, v)exactly
when ehas the color cP. We assign the coloring such that for two consecutive edges
e= (u, v)and e0= (v, w)it holds that at time tthe edge e0has always the color
that ehad at time t−1. This ensures that once a packet starts moving, it will
never stop until it reaches its destination.
3.3.1. Path Coloring. Now we describe the algorithm in detail. First we want to
find a coloring for the paths such that two paths with the same color do not share an
edge. We do this in two phases: in the first phase we consider each vertex vtogether
with its adjacent vertices (this subgraph forms a star). For each of these subgraphs
(together with the paths of the packets in this subgraph) we solve the path coloring
problem optimally (here we use the fact that our tree is directed). Then we combine
all these part-solutions and obtain a solution for the global path-coloring problem.
Phase one: Let vbe a vertex and denote by Tvthe subgraph induces by vand
its adjacent vertices. We want to find a coloring for the paths that use edges in
Tv. We reduce this problem to the edge-coloring problem on bipartite multigraphs
(note that it is crucial that the edges in Tvare directed):
Let Ube the set of vertices which have outgoing edges to v, i.e., U={u|(u, v)∈E}.
Similarly, let Wbe the set of vertices having ingoing edges from v, i.e., W=
{w|(v, w)∈E}. We construct an undirected graph Bvas follows: the set U∪W
forms the set of vertices in Bv. For each path Pthat goes from a vertex u∈U
through vto a vertex w∈Wwe introduce an edge eP:= {u, w}in Bv. For all paths
Pthat start in a vertex u∈Uand end in vwe introduce a new vertex wP∈W
and an edge eP:= {u, wP}in Bv. Similarly for paths Pthat start in vand end in
a vertex w∈Wwe add a vertex vPand introduce an edge eP:= {vP, w}in Bv.
Thus, for the maximum degree ∆ (Bv)of a node in Bvit holds that ∆ (Bv)≤C.
Also, it holds that two edges ePand eP0share an end-vertex if and only if their
corresponding paths Pand P0share an edge in Tv. Thus, a valid edge-coloring for
Bvimplies a valid path coloring for Tvand vice versa. Moreover, from the con-
struction it follows that Bvis bipartite. We compute a minimum edge coloring for
Bv(e.g., see [4]). The number of colors needed equals the maximum node degree
∆ (Bv)[4].
Phase two: Now we combine the found solutions for the graphs Tvone by one to
obtain a global solution (a similar construction is described in [6, Lemma 2]). We
start with an arbitrary vertex vand the path coloring of Tv. Now let v0be a vertex
adjacent to vand consider the graph Tv0. We permute the colors of the paths in Tv0
such that the paths that use the edge (v, v0)(or (v0, v), respectively) have the same
colors in Tvand Tv0. We iterate over the vertices by always adding a vertex that is
adjacent to one of the vertices that have been considered already. Eventually, for
each edge e= (u, v)all paths that use ehave the same color in Tuand Tv. Since T
is a tree in each iteration we can find a valid permutation of the colors of the paths
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 24
by using a simple greedy strategy. Since for each graph Tvwe find path colorings
with at most Ccolors, the resulting path coloring for Thas Ccolors as well.
3.3.2. Time-Dependent Coloring. Now we construct a time-dependent coloring c:
E×N→ {1,2, ..., C}with Ccolors for the edges of T. It has the consecutive
property: for two consecutive edges e= (u, v)and e0= (v, w)it holds that c(e, i) =
c(e0, i + 1). Since our graph is a directed tree such a coloring can be found with
a greedy method: Start with an arbitrary edge eand define its coloring c(e, i) :=
imod Cfor all i∈N. Then inductively assign the colors to the remaining edges
such that the consecutive property holds.
3.3.3. Routing Schedule. Finally we describe the schedule algorithm. To each packet
we assign the color of its path. Now let Mbe a packet on a vertex uthat needs to
use the edge e= (u, v)next. Let cPbe the color of M. We move Malong ein the
next timestep twith c(e, t) = cP. Denote by DTREE (I)the resulting schedule
for an instance I.
Theorem 13. Let Tbe a directed tree and let I= (T, M)be a packet routing
instance. It holds that |DT REE (I)| ≤ C+D−1. A packet is never delayed once
it has left its start vertex (direct routing). Moreover, DTREE (I)can be computed
in O¡n2log C¢.
Proof. Since no two packets with the same color share an edge there can be at most
one packet that uses an edge eat a time t. Each packet Mwaits in its origin vertex
for at most C−1timesteps. Due to the consecutive property once it left its start
vertex it moves to its destination without being delayed any further. Thus, the
length of the overall makespan is bounded by C−1 + D.
For the runtime analysis let n:= max {|M| ,|V|}. The edge coloring problem
on bipartite multigraphs can be solved optimally in O(mlog ∆) where mdenotes
the number of edges in the graph and 4the maximum node degree, see [4]. Thus,
computing the optimal path coloring for one graph Tvcan be done in O(nlog C)
and for all graphs Tvin O¡n2log C¢.
Then we need to combine the colorings for the graphs Tvto a global path coloring.
We say a path Ptouches a vertex vif Pit goes through v, starts in vor ends in
v. We pick an arbitrary vertex vand and color all paths which touch vin the
colors that they have in Tv. After this initialization we iterate by taking vertices
v0which are adjacent to already considered vertices. When we iterate we need to
pick a color for each uncolored path Pwhich touches v0. For doing this we need to
try at most C≤ncolors to find a color for Pin a valid color permutation for Tv0.
Since we have at most npaths to color and the order of the vertices v0is obtained
by a depth-first-search, the second phase can be done in O¡n2¢. This gives a total
runtime of O¡n2log C¢.¤
Note that the bound C+D−1is the best bound we can give in terms of C
and Dsince there are packet routing instances which need this many steps. E.g.,
consider a path of length Dwith vertices v1, ..., vDand Cpackets all having as
start vertex v1and as destination vertex vD.
In the construction used in the proof of Theorem 11 the lengths of the paths
for all packets are all equal and the FDF-algorithm may find a very bad schedule.
However, when we require the lengths of the paths of the packets to be pairwise
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 25
level 0
level 1
level 2
level 3
level 4
Figure 3.4. The partitioning of a directed tree into five levels.
The destination vertices of the packets are filled with the color of
the respective packets. Note that for the definition of the level of a
vertex we cannot just take the maximum distance to a leave since
then, e.g., the light gray vertex would be in level 0 rather than in
level 2.
different, we can find a direct schedule of length Don directed trees in polynomial
time.
Let T= (V, A)be a directed tree and let I= (T, M)be a packet routing instance
such that the lengths of the paths of the packets are pairwise different. Note that we
can assume that all leaves in Tare either start or destination vertices of packets.
First we partition the packets into different levels (see Figure 3.4). In order to
measure the level distance between two packets we introduce the notion of directed
distance.
Definition 14 (directed distance).Let T0be the underlying undirected tree of T.
Let uand vbe two vertices and let P= (u0=u, u1, u2, ..., uk=v)be the unique
simple path from uto vin T0. We define
w(ui, uj) := (+1 if (ui, uj)∈A
−1 if (uj, ui)∈A
The directed distance d(u, v)between uand vis defined by
d(u, v) :=
k
X
i=0
w(ui, uj)
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 26
For each vertex vwe define its level by l(v) := maxv0∈Vd(v, v0). For a sketch of
the levels of a directed graph, see Figure 3.4. The directed distance between two
vertices equals in fact the difference of their levels: d(u, v) = l(u)−l(v).
For a packet M= (s, t)we define its start level by sl (M) := l(s)and its
destination level by dl (M) := l(t). Now we sort the packets by their destination
levels. We define Mi:= {M|dl (M) = i}. Since the lengths of the paths of the
packets are pairwise different, for each two packets M∈ Miand M0∈ Miit holds
that sl (M)6=sl (M0).
If for all pairs of packets Mand M0we could guarantee that sl (M)6=sl (M0)
then we could immediately obtain a direct schedule by greedily always moving all
packets. Clearly, this schedule would be optimal since each packet is sent directly
to its destination vertex without being delayed at all. However, in general different
packets may have the same start level. Nevertheless, we can compute a one-one
map vl :M → Nsuch that
•vl (M)6=vl (M0)if M6=M0,
•vl (M)≥sl (M)and
•vl (M)−dl(M)≤Dfor all packets M.
The intuition behind this is that we assign each packet Ma new virtual start
level vl(M)such that vl(M)is not smaller than sl(M)(intuitively speaking: the
new start level is “higher up” than the original one). Assuming the map vl as the
level assignment of the packets, we can construct a (virtual) direct routing schedule
by greedily moving all packets at all timesteps. The length of this schedule is at
most D, since vl (M)−dl(M)≤Dfor all packets M.
When computing a routing schedule for Iwe can simulate the virtual schedule
described above. First we compute vl. Then we schedule the packets as follows: A
packet M= (s, t)waits in sfor vl(M)−sl(M)timesteps (from the first property
of vl this is non-negative). Then it moves to twithout being delayed any further.
Denote by DTPD(I)(“directed tree path-lengths pairwise different”) the resulting
schedule.
In order to compute vl we inductively define maps li:M → N. We begin with
l0(M) := d(s, t)for all packets M= (s, t). Assume the maps l0, ..., lkare computed
already. When computing lk+1 for all packets M∈Si≤kMiwe fix their values
from lk. The values for all other packets are increased by at least one. Algorithm 3.1
shows the computation in detail. See Figure 3.5 for a sketch of the inductive steps.
Theorem 15. Let Tbe a directed tree and I= (T, M)be a packet routing in-
stance such that the lengths of the paths of the packets are pairwise different. Then
the schedule DTPD(I)is optimal with |DTPD(I)|=D. The computation of
DTPD(I)can be done in O¡n2¢.
Proof. First we need to show that vl is one-one and for all packets Mit holds that
vl (M)≥sl (M)and vl (M)≤D+dl(M). We give a proof by induction.
The map l0is one-one since the lenghts of the packets are pairwise different.
Moreover, it holds that l0(M)≤D+ 0. For induction we assume that lk(M)≤
D+kand lkis one-one. Since we defined lk+1 (M1) := D+k+ 1 it follows
that lk+1 (M1)> lk+1 (M)for all packets M∈Si≤kMi. From the definition of
lk+1 (M0)for packets M0∈Si>k Miand the induction hypothesis it follows that
lk+1 is one-one. Moreover, for all packets Mit holds that lk+1(M)≤lk+1 (M1)
which implies that lk+1(M)≤D+k+ 1.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 27
1
2
3
4
5
6
l0l1l2
Figure 3.5. The inductive steps for the construction of h0. The
circles denote packets whose values are not redefined after the re-
spective iteration.
Let Mbe a packet. We want to prove that vl (M)≤D+dl(M). For l0it clearly
holds that l0(M)≤D+dl(M). Now assume that lk(M)≤D+dl(M). For the
packet M1we have that lk+1 (M1) = D+k+ 1 ≤D+dl (M1). If M∈Si>k Miwe
know that lk+1 (M)< lk+1 (M1) = D+k+1 ≤D+dl(M). If M∈Si≤kMiit holds
that lk(M) = lk+1 (M)and thus the claim follows from the induction hypothesis.
Now we want to show that vl (M)≥sl (M). Let Mbe a packet with dl(M) = k.
Then in the first kiterations of the computation of vl the respective value for M
was strictly increased. Formally, l0(M)< l1(M)< ... < lk−1(M)< lk(M) =
lk+1(M) = lk+2(M) = ... =lMAX (M) = vl(M). We conclude that vl(M)≥
l0(M) + k=dist (s, t) + dl(M) = sl(M).
Now we show that DT PD(I)is a valid schedule. Let Mi= (si, ti)be a packet.
Denote by vi,τ the vertex where Miis located at time τ. Throughout this proof
we assume that τ≥0. We call Miactive at time τif vl (Mi)−sl (Mi)≤τand
vl (Mi)−τ > dl (Mi). Intuitively speaking, a packet is active at time τif it moves
at time τ. Note that if a packet Miis active then l(vi,τ ) = vl (Mi)−τ.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 28
Algorithm 3.1: Computation of the map vl
foreach M= (s, t)∈ M do1
l0(M) := dist (s, t);2
end3
K:=max {dl(M)|M∈ M};4
for k=1 to Kdo5
let MS:= Si≤kMi;
6
let ML:= Si>k Mi;7
foreach M∈ MSdo8
lk(M) := lk−1(M);9
end10
let M1∈MLbe the packet with lk(M1)≥lk(M)for all packets M∈ ML;11
lk(M1) := D+k+ 1;12
foreach M∈ MLdo13
let pbe the minimum value such that p>lk(M)and ∃M0∈ MLwith14
lk(M0) = p;
lk(M) := p;15
end16
end17
We claim that for two active packets Miand Mjit holds that l(vi,τ )6=l(vj,τ ).
Assume on the contrary that there are two active packets Miand Mjand a value
for τwith l(vi,τ ) = l(vj,τ )in DTPD(I). Also assume that τis the first time that
this happens in DTPD(I). Since both packets are active and thus vl (Mi)−τ=
l(vi,τ ) = l(vj,τ ) = vl (Mj)−τwe conclude that vl (Mi) = vl (Mj). But this is
a contradiction since vl is one-one. Thus, in DT PD(I)no two packets are ever
located on the same vertex and, therefore, DT PD(I)is a direct schedule.
Now we prove that |DT PD(I)|=D. From the definition of the algorithm and
since DTPD(I)is a direct schedule it follows that l(vi,τ ) = max {min {vl (Mi)−τ, sl (Mi)}, dl (Mi)}
for all packets Miand all τ. We already showed that vl (Mi)≤D+dl (Mi). Note
that this implies that vl (Mi)−D≤D+dl (Mi)−D=dl (Mi)≤sl (Mi)and thus
l(vi,D) = max {min {vl (Mi)−D, sl (Mi)}, dl (Mi)}= max {vl (Mi)−D, dl (Mi)}.
Putting things together we conclude that
l(vi,D) = max {vl (Mi)−D, dl (Mi)}
≤max {(D+dl (ti)) −D, dl (Mi)}
=dl (Mi)
This shows that after at most Dsteps Mihas reached ti. Since for the computation
of DTPD(I)we only need to state how long each packet has to wait in its start
vertex the computation of vl dominates the runtime of the algorithm. The map vl
can be computed in O¡n2¢and thus the computation of DT P D(I)can be done in
O¡n2¢.¤
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 29
4. Conclusion
We investigated the packet routing problem with fixed and variable paths. A
variant, the delay routing problem has already been shown to be NP-hard [15].
We proved that the packet routing problem is also NP-hard (for fixed and variable
paths), and that there can be no polynomial time approximation schemes (PTAS)
for it unless P=NP. This holds even if we restrict the considered graph class to
directed trees.
All NP-hardness results rely on constructing a gap of one timestep between yes-
and no-instances of the 3-SAT variant that we reduce from. This raises the question
whether there is an approximation algorithm with an absolut error. We answered
this question in the negative. We proved that there is no approximation algorithm
with an absolute error of kfor any k≥0for the packet routing problem unless
P=NP. This holds even for planar graphs. It would be interesting to investigate
whether on trees an absolute approximation is possible.
We showed that the FDF-algorithm can perform arbitrarily bad even on directed
trees due to bad tie-breaking decisions. However, we showed how it can be used in
a beneficial manner to obtain a 2-approximation for packet routing in undirected
trees. For directed trees we can do even better. We presented an algorithm that
finds a direct routing schedule of length at most C+D−1. In cases where C
is known to be significantly smaller than D(or vice versa) this gives a provably
better approximation than 2. For direct routing on undirected trees the best known
result is a schedule of length 2C+D−2yielding a 3-approximation [3]. Our 2-
approximation for general trees is the first step towards approximation algorithms
that do not rely on Cand Das lower bounds. This is very desirable since our
bound of C+D−1is the best one can guarantee in terms of Cand D.
For the setting that the lengths of the paths of the packets are pairwise different,
we presented an optimal algorithm for directed trees which computes a schedule of
length D. It is interesting to find more classes of packet routing instances which
allow schedules of that length and algorithms to compute these schedules.
Acknowledgements. We would like to thank Joachim Reichel, Ronald Koch and
Daniel Plümpe for helpful discussions.
References
[1] M. Adler, S. Khanna, R. Rajaraman, and A. Rosénbusch. Time-constrained scheduling of
weighted packets on trees and meshes. In Proceedings of the 11th annual ACM Symposium
on Parallel Algorithms and Architectures, pages 1–12, 1999.
[2] F. Meyer auf der Heide and B. Vöcking. Shortest-path routing in arbitrary networks. Journal
of Algorithms, 31, 1999.
[3] C. Busch, M. Magdon-Ismail, M. Mavronicolas, and P. Spirakiscac. Direct routing: Algo-
rithms and complexity. In Proceedings of the 12th Annual European Symposium on Algo-
rithms, volume 3221 of LNCS, pages 134–145, 2004.
[4] R. Cole, K. Ost, and S. Schirra. Edge-coloring bipartite multigraphs in O(Elog D)time.
Combinatorica, 21:5–12, 2001.
[5] W. J. Cook, L. Lovász, and J. Vygen, editors. Research Trends in Combinatorial Optimiza-
tion. Springer, 2009.
[6] T. Erlebach and K. Jansen. The complexity of path coloring and call scheduling. Theoretical
Computer Science, 255:33–50, 2001.
[7] L. Fleischer and M. Skutell. Quickest flows over time. SIAM Journal on Computing, 36:1600–
1630, 2007.
PACKET ROUTING: COMPLEXITY AND ALGORITHMS 30
[8] L. Fleischer and M. Skutella. Minimum cost flows over time without intermediate storage.
In Proceedings of the 14th Annual ACM–SIAM Symposium on Discrete Algorithms, pages
66–75, Baltimore, MD, 2003.
[9] L. R. Ford and D. R. Fulkerson. Constructing maximal dynamic flows from static flows.
Operations Research, 6:419–433, 1958.
[10] L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
[11] M. Garey and D. Johnson. Computers and Intractability: A Guide to the theory of NP-
completeness. Freeman NY, 1979.
[12] A. Hall, S. Hippler, and M. Skutella. Multicommodity flows over time: Efficient algorithms
and complexity. Theoretical Computer Science, 2719:397–409, 2003.
[13] A. Hall, K. Langkau, and M. Skutella. An FPTAS for quickest multicommodity flows with
inflow-dependent transit times. Algorithmica, 47:299–321, 2007.
[14] B. Hoppe and É. Tardos. The quickest transshipment problem. In Proceedings of the 6th
annual ACM-SIAM Symposium on Discrete Algorithms, pages 512–521, 1995.
[15] M. Di Ianni. Efficient delay routing. In 2nd International EURO-PAR Conference, volume
1123 of LNCS, 1996.
[16] R. Koch, B. Peis, M. Skutella, and A. Wiese. Real-time message routing and scheduling.
Technical Report 006-2009, Technische Universität Berlin, February 2009.
[17] F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job-scheduling in
O(congestion +dilation)steps. Combinatorica, 14:167–186, 1994.
[18] F. T. Leighton, B. M. Maggs, and A. W. Richa. Fast algorithms for finding O(congestion +
dilation)packet routing schedules. Combinatorica, 19:375–401, 1999.
[19] J. Y.-T. Leung. Handbook of Scheduling: Algorithms, Models and Performance Analysis.
2004.
[20] Y. Mansour and B. Patt-Shamir. Greedy packet scheduling on shortest paths. Journal of
Algorithms, 14, 1993.
[21] R. Ostrovsky and Y. Rabani. Universal O(congestion +dilation + log1+²N)local control
packet switching algorithms. In Proceedings of the 29th annual ACM Symposium on Theory
of Computing, pages 644–653, 1997.
[22] B. Peis, M. Skutella, and A. Wiese. Packet routing: Complexity and algorithms. Technical
Report 003-2009, Technische Universität Berlin, February 2009.
[23] Y. Rabani and É. Tardos. Distributed packet switching in arbitrary networks. In Proceedings
of the 28th annual ACM Symposium on Theory of Computing, pages 366–375. ACM, 1996.
[24] A. Srinivasan and C.-P. Teo. A constant-factor approximation algorithm for packet routing
and balancing local vs. global criteria. SIAM Journal on Computing, 30, 2001.
[25] D. P. Williamson, L. A. Hall, J. A. Hoogeveen, C. A. J. Hurkens, J. K. Lenstra, S. V.
Sevast’janov, and D. B. Shmoys. Short shop schedules. Operations Research, 45:288–294,
1997.
