**An algorithmic toolbox for Network Calculus.**
A. Bouillard and E. Thierry.

**News!** An implementation of some of our algorithms has been achieved by
Sébastien Lagrange.

**Errata** (many thanks to Jorn Migge) :

** • Statement of Lemma 13 (page 26):** if *a=0* and *f(a+)<0* then *f*^{∗}=−∞
over *R*_{+}^{∗}.

** • Proofs of Lemma 11 (page 26) and Lemma 14 (page 27):** the case *T=0* and *f(T)<0* for spots
and the case *T=0* and *f(T+)<0* for open segments are not treated in Lemma 1. For those cases a simple
yet special lemma is necessary : for spots if *T=0* and *f(T)<0* then *f*^{∗}(t)=−∞
for all *t≥0* and for open segments if *T=0* and *f(T+)<0* then *f*^{∗}(t)=−∞
for all *t>0*.

** • Proof of Lemma 14 - several typos in inequalities:**

In the case *c/d≤ρ* and *f(T+)/T≤c/d*, after "Such an integer *K* exists since" (page 29),
replace "*0≤ρ-c/d<ρ-f(T+)/T*" by "*ρ-c/d≤ρ-f(T+)/T*" (*0≤ρ-c/d* is true,
but not necessary for the existence of *K*).

In the case *c/d≤ρ* and *f(T+)/T>c/d*, after "Such an integer *K* exists since" (page 30),
replace "*0≤ρ-f(T+)/T<ρ-c/d*" by "*ρ-f(T+)/T<ρ-c/d*" (since *ρ-f(T+)/T* can be negative).

Extend the case *c/d>ρ* and *f(T+a+)/(T+a)>c/d* to *c/d>ρ* and *f(T+a+)/(T+a)≥c/d*, and
after "Such an integer *K* exists since" (page 31), replace "*0< c/d-ρ< f(T+a+)/(T+a)-ρ*" by
"*c/d-ρ≤f(T+a+)/(T+a)-ρ*" (*0< c/d-ρ* is true but not necessary).

The last case *c/d>ρ* and *f(T+a+)/(T+a)< c/d* (page 31) is ok.

** • Statement and Proof of Lemma 11 (resp. Lemma 14):** the cases when *T=0* and *f(T)>0* or *f(T)=0*
(resp. *f(T+)>0* or *f(T+)=0*) are not explicitely treated since the cases in the paper refer to *f(T)/T*
(resp. *f(T+)/T*) which have to be defined here:

Case *T=0* and *f(T)>0* (resp. *f(T+)>0*): do as if *f(T)/T=+∞* (resp. *f(T+)/T=+∞*).

Case *T=0* and *f(T)=0* (resp. *f(T+)=0*): do as if *f(T)/T=c/d* (resp. *f(T+)/T=c/d*).

** • Proof of Proposition 4 (page 15-18):** two important remarks (present in a former technical report) are missing in the paper ! In particular,
one special case in the proof of Proposition 9 refers to one of those remarks about the preservation of ultimate pseudo-periodicity for
the convolution when one input function is not ultimately plain, which uses itself a first remark about such a preservation for the minimum.

The text below must be added at the end of Point 1. (and 2.) (minimum and maximum) in the proof of Proposition 4 (page 16):

*
"As a complement, note that if **c'*_{1}≤c'_{2}, another way to
ensure that *min(f*_{1},f_{2}) is locally bounded, ultimately plain and
pseudo-periodic, is to keep locally bounded and pseudo-periodicity assumptions on inputs but
suppose that only *f*_{1} is ultimately plain with *∀ t ≥ T*_{1},
*f*_{1}(t) ∈ **R** and that *f*_{2} is not necessarily ultimately
plain (it may have *+∞* values from *T*_{2}) but *∀ t ≥ T*_{2},
*f*_{2}(t) ≠ −∞. If *c'*_{1}=c'_{2}, the minimum is still
clearly plain and pseudo-periodic from *max(T*_{1},T_{2}). If *c'*_{1} < c'_{2},
then proceed exactly as above (we still have *M*_{1}<+∞ and *m*_{2}>−∞)
and remark that *min(f*_{1},f_{2}) is clearly ultimately plain from *T*_{1}."

The text below must be added at the end of Point 5. (convolution) in the proof of Proposition 4 (page 17) :

*
"As a complement, note that to preserve the ultimate pseudo-periodicity, we only need one input function to be ultimately
plain as shown now. Suppose that **f*_{1} is ultimately plain
from *T*_{1} (here possibly *∈ ***R** or *=+∞* or *=−∞*), but
that *f*_{2} is not necessarily ultimately plain. We first dismiss the
case treated in Lemma 1 when *∃ a ∈ ***R**_{+},
*f*_{1}(a)=−∞ or *f*_{2}(a)=−∞, both leading to
*f*_{1}*f_{2}=−∞ from *a*, i.e. an ultimately plain pseudo-periodic
output. In the reasoning, the first term *f'*_{1}*f'_{2} is still equal
to *+∞* from *T*_{1}+T_{2}, and we consider two cases depending of
*f''*_{1} which represents the ultimate behaviour of *f*_{1}:

- If *f''*_{1}=+∞ all over **R**_{+}, then
*f''*_{1}*f'_{2}=f''_{1}*f''_{2}=+∞ all over **R**_{+}. Since
*f'*_{1}*f'_{2}=+∞ from *T*_{1}+T_{2}, we have *f*_{1}*f_{2}=f'_{1}*f''_{2}
from *T*_{1}+T_{2} which is ultimately pseudo-periodic with
period *d*_{2} and increment *c*_{2}. But it is not necessarily
ultimately plain (e.g. choose *f*_{1}(t)=0 if *t=0* and *=+∞*
otherwise, and *f*_{2}(t)=t if *t* is an even integer and *=+∞*
otherwise, and then *f*_{1}*f_{2}=f_{2}).

- If *f''*_{1}(t) ∈ **R** from *T*_{1}, then either *∃ a ≥
T*_{2}, *f''*_{2}(a) ∈ **R** or *f''*_{2}=+∞ all over **R**_{+}. In the
first case, *f''*_{1}*f''_{2} is ultimately plain with values in **R**
from *T*_{1}+a. Since it is ultimately pseudo-periodic with period *d* and
increment *min(c'*_{1},c'_{2}), whereas *f'*_{1}*f''_{2} and *f''*_{1}*f'_{2}
are ultimately pseudo-periodic with same period but larger
increments (resp. *c'*_{2} and *c'*_{1}), their minimum is ultimately
plain and pseudo-periodic (see the complement in the study of the
minimum). In the second case when *f''*_{2}=+∞ all over **R**_{+},
*f*_{1}*f_{2}=f''_{1}*f'_{2} from *T*_{1}+T_{2} which is also clearly ultimate
plain and pseudo-periodic."

** • Inputs of Algorithm 2 (page 37):** as mentionned in Proposition 4, this algorithm will work for a larger set of inputs. In the description
of the input data, replace "*f*_{1},f_{2} both ultimately plain and pseudo-periodic" by the following valid cases (which cover this
previous case) "*f*_{1},f_{2} both ultimately pseudo-periodic, with *f*_{1} ultimately plain and
*c*_{1}/d_{1} ≤ c_{2}/d_{2}, or *f*_{2} ultimately plain and *c*_{2}/d_{2}
≤ c_{1}/d_{1}". One should also change the presentation just above by adding to "it works if they are both
ultimately plain" the others cases "or if *f*_{1} ultimately
plain and pseudo-periodic and *c*_{1}/d_{1} ≤ c_{2}/d_{2}, or
*f*_{2} ultimately plain and pseudo-periodic and *c*_{2}/d_{2} ≤ c_{1}/d_{1}".

** • Inputs of Algorithm 3 (page 40):** change the description of the input data into "both ultimately pseudo-periodic, and at least one ultimately plain."
since it is necessary as mentioned in the text before the algorithm.

**Optimal routing for end-to-end guarantees using Network Calculus.**
A. Bouillard, B. Gaujal, S. Lagrange and E. Thierry.

This paper deals with the same routing problem as the Valuetools'2007 paper.
It solves in polynomial time the general "shortest path" problem left open
in Valuetools'2007, but does not present the Valuetools algorithms designed
for particular cases (simpler and thus with lower complexity). Moreover it
shows that the nice Valuetools algorithm to compute the multi-dimensional
convolution has a flaw. We did not manage to correct this algorithm or
specify the additional assumptions necessary to make it work. We only
present a special case where the computation is easy.

**News !** It appears that searching a path which achieves some end-to-end
delay requirement (decision problem) in a Network Calculus model, has been
discussed in S. Recker, "Service curve based routing subject to deterministic
QoS constraints", Telecommunication Systems 24, pages 385-413, 2003, and
M. Fidler, S. Recker, "Conjugate network calculus: a dual approach
applying the Legendre transform", Computer Networks 50, pages 1026-1039, 2006.
Their idea of using Legendre transform to simplify the problem is similar to
ours. However the algorithms presented in those papers are not fully analyzed
and there is no clear reference to the classical shortest path algorithms with additive
weights.

**Greedy algorithms for optimization on distance-hereditary graphs.**
O. Cogis, E. Thierry.

Although it is difficult to provide formal definitions of "greedy algorithms" or
"dynamic programming" covering exactly their use in the literature, it is clear
that the term "greedy" is inappropriate in most of this work and it should be replaced
by "dynamic programming" (during the process of building a solution, the algorithms
advance by maintaining several candidate-solutions of subproblems).

**Computational aspects of the 2-dimension of partially ordered sets.**
M. Habib, L. Nourine, O. Raynaud and E. Thierry.

Several sources indicate several articles where the computation of the
2-dimension or more generally the *k*-dimension has been showed NP-hard first.
Here are some candidates:
Unfortunately we did not manage to check whether those references actually
contain such proofs.

**Errata**

**• Statement of Proposition 13 (page 411):** replace *max(|J(L)|,|M(L)|)* par *min(|J(L)|,|M(L)|)*.

**Extending a partially ordered set: links with its lattice of ideals.**
P. Baldy, M. Morvan and E. Thierry.

Concerning the bijection between the linear extensions of a poset and the maximal chains
of its lattice of ideals, Stefan Felsner
has suggested another link with the linear-extension graph.

**Optimal routing for end-to-end guarantees: the price of multiplexing.**
A. Bouillard, B. Gaujal, S. Lagrange and E. Thierry.

This paper contains several errors which are listed and explained in the Performance 2008
journal version. We managed to patch some of them, but not all of them.

**Dynamics of the Picking transformation on integer partitions.**
H. D. Phan Ti and E. Thierry.

**News !** It appears that this transformation has been previously
studied under the name "*Bulgarian solitaire*". The main results of
our article have already been proved and some of our conjectures have been
solved. A survey of these results may be found here.
Thanks to Kyle Petersen for letting us
know.

**A quasi optimal bit-vector encoding of tree hierarchies. Application to efficient type inclusion tests.**
O. Raynaud and E. Thierry.

**News !** An improvement of our algorithm has been presented at the next *ECOOP'2002*
by Robert E. Filman with
"polychotomic encodings".

**News !** We have presented at *MCO'2008* a new algorithm computing arbitrarily
smaller bit vector encodings than polychotomic encodings. However the complexity of computing
the 2-dimension for trees remains an open problem.

**Generating random permutations in the framework of parallel coarse grained models.**
I. Guérin-Lassous and E. Thierry.

**News !** A solution verifying simultaneously our three main criteria has
been presented by Jens Gustedt,
"Efficient Sampling of Random Permutations", Journal of Discrete Algorithms 6(1), pages 125-139, 2008
(download the 2002 Inria report).