/tropical-convolution

efficient convolution in (min,+) algebra

Primary LanguageC++MIT LicenseMIT

tropical-convolution

Build Status

efficient convolution in (min,+) algebra.

Compute $c[k] = \min_{i} a[i] + b[k-i]$ for all values of k efficiently with the algorithm described in M. Bussieck, H. Hassler, G. J. Woeginger, and U. T. Zimmermann: Fast algorithms for the maximum convolution problem. Oper. Res. Let. , 15:1–5, 1994.