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 条

[11] Fast Algorithms for Knapsack via Convolution and Prediction
Bateni, MohammadHossein
Hajiaghayi, MohammadTaghi
Seddighin, Saeed
Stein, Cliff
STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 1269 - 1282
[12] Automatic derivation and implementation of fast convolution algorithms
Johnson, JR
Breitzman, AF
JOURNAL OF SYMBOLIC COMPUTATION, 2004, 37 (02) : 261 - 293
[13] FAST ALGORITHMS FOR THE MAXIMUM CLIQUE PROBLEM ON MASSIVE GRAPHS WITH APPLICATIONS TO OVERLAPPING COMMUNITY DETECTION
Pattabiraman, Bharath
Patwary, Md. Mostofa Ali
Gebremedhin, Assefaw H.
Liao, Wei-keng
Choudhary, Alok
INTERNET MATHEMATICS, 2015, 11 (4-5) : 421 - 448
[14] Fast Algorithms for Foggy Image Enhancement Based on Convolution
Chen Xianqiao
Yan Xinping
Chu Xiumin
PROCEEDINGS OF THE 2008 INTERNATIONAL SYMPOSIUM ON COMPUTATIONAL INTELLIGENCE AND DESIGN, VOL 2, 2008, : 165 - +
[15] BRUTE-FORCE SEARCH OF FAST CONVOLUTION ALGORITHMS
Haynal, Steve
Haynal, Heidi
2013 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2013, : 2586 - 2590
[16] Algorithms for the maximum hamming distance problem
Angelsmark, O
Thapper, J
RECENT ADVANCES IN CONSTRAINTS, 2005, 3419 : 128 - 141
[17] Evolutionary algorithms and the maximum matching problem
Giel, O
Wegener, I
STACS 2003, PROCEEDINGS, 2003, 2607 : 415 - 426
[18] Survey on algorithms for the maximum satisfiability problem
He, Kun
Zheng, Jiongzhi
Huazhong Keji Daxue Xuebao (Ziran Kexue Ban)/Journal of Huazhong University of Science and Technology (Natural Science Edition), 2022, 50 (02): : 82 - 95
[19] On comparing algorithms for the maximum clique problem
Zuge, Alexandre Prusch
Carmo, Renato
DISCRETE APPLIED MATHEMATICS, 2018, 247 : 1 - 13
[20] MAXIMUM r-REGULAR INDUCED SUBGRAPH PROBLEM: FAST EXPONENTIAL ALGORITHMS AND COMBINATORIAL BOUNDS
Gupta, Sushmita
Raman, Venkatesh
Saurabh, Saket
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (04) : 1758 - 1780

← 1 2 3 4 5 →