Fast algorithms for the maximum convolution problem

M. Bussieck, H. Hassler, G.J. Woeginger, U.T. Zimmermann

    Research output: Contribution to journalArticleAcademicpeer-review

    13 Citations (Scopus)
    1 Downloads (Pure)


    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 languageEnglish
    Pages (from-to)133-141
    Number of pages9
    JournalOperations Research Letters
    Issue number3
    Publication statusPublished - 1994


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

    Cite this