[boost] Min-Plus Algebra (Dioid) and Min-Plus Convolution

From: Reetesh Mukul (reetesh.mukul_at_[hidden])
Date: 2006-09-23 13:30:58

Hi,

Is there any interest in a library for min-plus (dioid) algebra and min-plus
convolution. In min-plus algebra sum is replaced by minimum operator, while
product is replaced by sum operator. Thus, here,

(3+4)*5 = min(3,4) + 5 = 3 + 5 = 8.

Min-plus convolution is convolution of flow curves, for example, for flows
in Computer Networks. It goes like this :-

(f conv g)(t) = min(f(s) + g(t-s)).

These convolutions will be important for deterministic characterization of
networks. We have implemented peak rate, affine, ratelatency and piecewise
linear curves and corresponding convolutions. These whole thing will be
applicable to wide areas starting from piecewise approximation of curves to
simulation of flow equations.

Regards,
Reetesh Mukul