### Abstract

We describe two algorithms for solving the maximum convolution problem, i.e. the calculation of ck: = max {ak-i + bi 0 i n - 1} for all k with respect to given sequences (a0…, an-1), (b0,…, bn-1), of real numbers. Our first algorithm with expected running time O (n log n) is mainly of theoretical interest while our second algorithm allows a simpler, more practicable implementation and showed quite fast performance in numerical experiments.

Original language | English |
---|---|

Pages (from-to) | 133-141 |

Number of pages | 9 |

Journal | Operations Research Letters |

Volume | 15 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1994 |

## Fingerprint Dive into the research topics of 'Fast algorithms for the maximum convolution problem'. Together they form a unique fingerprint.

## Cite this

Bussieck, M., Hassler, H., Woeginger, G. J., & Zimmermann, U. T. (1994). Fast algorithms for the maximum convolution problem.

*Operations Research Letters*,*15*(3), 133-141. https://doi.org/10.1016/0167-6377(94)90048-5