FAST ALGORITHMS FOR THE MAXIMUM CONVOLUTION PROBLEM

被引：12

作者：

BUSSIECK, M

HASSLER, H

WOEGINGER, GJ

ZIMMERMANN, UT

机构：

[1] TECH UNIV CAROLO WILHELMINA BRAUNSCHWEIG,MATH OPTIMIERUNG ABT,POCKELSSTR 14,D-38106 BRAUNSCHWEIG,GERMANY

[2] GRAZ TECH UNIV,INST ANGEW INFORMAT & KOMMUNIKAT TECHNOL,A-8010 GRAZ,AUSTRIA

[3] GRAZ TECH UNIV,INST THEORET INFORMAT,A-8010 GRAZ,AUSTRIA

来源：

OPERATIONS RESEARCH LETTERS | 1994年 / 15卷 / 03期

关键词：

MAXIMUM CONVOLUTION; PROBABILISTIC ANALYSIS;

D O I：

10.1016/0167-6377(94)90048-5

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We describe two algorithms for solving the maximum convolution problem, i.e. the calculation of c(k): = max {a(k-i) + b(i)\0 less-than-or-equal-to i less-than-or-equal-to n-1} for all k with respect to given sequences (a0, ..., a(n-1)), (b0, ..., b(n-1), of real numbers. Our first algorithm with expected running time 0(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.

引用

页码：133 / 141

页数：9

共 50 条

[21] Optimally fast parallel algorithms for maximum problems
Tsotras, V.J.
Proceedings of the European Workshops on Parallel Computing, 1992,
[22] Fast Maximum Clique Algorithms for Large Graphs
Rossi, Ryan A.
Gleich, David F.
Gebremedhin, Assefaw H.
Patwary, Md Mostofa Ali
WWW'14 COMPANION: PROCEEDINGS OF THE 23RD INTERNATIONAL CONFERENCE ON WORLD WIDE WEB, 2014, : 365 - 366
[23] A fast algorithm for the maximum clique problem
Östergård, PRJ
DISCRETE APPLIED MATHEMATICS, 2002, 120 (1-3) : 197 - 207
[24] Fast relaxed algorithms of maximum variance unfolding
Wang, Qinggang
Li, Jianwei
Jisuanji Yanjiu yu Fazhan/Computer Research and Development, 2009, 46 (06): : 988 - 994
[25] Algorithms for the problem of K maximum sums and a VLSI algorithm for the K maximum subarrays problem
Bae, SE
Takaoka, T
I-SPAN 2004: 7TH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS AND NETWORKS, PROCEEDINGS, 2004, : 247 - 253
[26] FAST DCT-BASED ALGORITHMS FOR SIGNAL CONVOLUTION AND TRANSLATION
Bilevich, Leonid
Yaroslavsky, Leonid
2009 16TH INTERNATIONAL CONFERENCE ON DIGITAL SIGNAL PROCESSING, VOLS 1 AND 2, 2009, : 898 - 903
[27] A CLASS OF FAST CYCLIC CONVOLUTION ALGORITHMS BASED ON BLOCK PSEUDOCIRCULANTS
TEIXEIRA, M
RODRIGUEZ, D
IEEE SIGNAL PROCESSING LETTERS, 1995, 2 (05) : 92 - 94
[28] Enabling Efficient Fast Convolution Algorithms on GPUs via MegaKernels
Jia, Liancheng
Liang, Yun
Li, Xiuhong
Lu, Liqiang
Yan, Shengen
IEEE TRANSACTIONS ON COMPUTERS, 2020, 69 (07) : 986 - 997
[29] The maximum capture problem with random utilities: Problem formulation and algorithms
Benati, S
Hansen, P
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 143 (03) : 518 - 530
[30] Oblivious Algorithms for the Maximum Directed Cut Problem
Feige, Uriel
Jozeph, Shlomo
ALGORITHMICA, 2015, 71 (02) : 409 - 428

← 1 2 3 4 5 →