Fast algorithms for the maximum convolution problem

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

    Research output: Contribution to journalArticleAcademicpeer-review

    11 Citations (Scopus)
    1 Downloads (Pure)

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

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

  • Cite this