Selection on X1

被引：2

作者：

Kreitzberg, Patrick ^{[1
]}

Lucke, Kyle ^{[2
]}

Pennington, Jake ^{[1
]}

Serang, Oliver ^{[2
]}

机构：

[1] Univ Montana, Dept Math, Missoula, MT 59812 USA

[2] Univ Montana, Dept Comp Sci, Missoula, MT 59812 USA

来源：

PEERJ COMPUTER SCIENCE | 2021年

基金：

美国国家科学基金会;

关键词：

Selection; Cartesian product; Tree; Sorting; CONVOLUTION;

D O I：

10.7717/peerj-cs.483

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on A+B, based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of A+B selections was proposed to perform selection on X-1+X-2+...+X-m in o(n.m+k.m), where X-i have length n. Here, that o(n.m+k.m) algorithm is combined with a novel, optimal LOH-based algorithm for selection on A+B (without a soft heap). Performance of algorithms for selection on X-1+X-2+...+X-m are compared empirically, demonstrating the benefit of the algorithm proposed here.

引用

页数：11

共 14 条

[1] Necklaces, Convolutions, and X plus Y
Bremner, David
Chan, Timothy M.
Demaine, Erik D.
Erickson, Jeff
Hurtado, Ferran
Iacono, John
Langerman, Stefan
Patrascu, Mihai
Taslakian, Perouz
[J]. ALGORITHMICA, 2014, 69 (02) : 294 - 314
[2] FAST ALGORITHMS FOR THE MAXIMUM CONVOLUTION PROBLEM
BUSSIECK, M
HASSLER, H
WOEGINGER, GJ
ZIMMERMANN, UT
[J]. OPERATIONS RESEARCH LETTERS, 1994, 15 (03) : 133 - 141
[3] The soft heap: An approximate priority queue with optimal error rate
Chazelle, B
[J]. JOURNAL OF THE ACM, 2000, 47 (06) : 1012 - 1027
[4] THE COMPLEXITY OF SELECTION AND RANKING IN X + Y AND MATRICES WITH SORTED COLUMNS
FREDERICKSON, GN
JOHNSON, DB
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1982, 24 (02) : 197 - 208
[5] Fredman M. L., 1976, Theoretical Computer Science, V1, P355, DOI 10.1016/0304-3975(76)90078-5
[6] SELECTING KTH ELEMENT IN X+Y AND X1+X2+ ... +XM
JOHNSON, DB
MIZOGUCHI, T
[J]. SIAM JOURNAL ON COMPUTING, 1978, 7 (02) : 147 - 153
[7] Kaplan H, 2019, S SIMPLICITY ALGORIT, V69
[8] Kreitzberg P., 2020, ARXIV PREPRINT ARXIV
[9] Kreitzberg P, 2021, J MACH LEARN RES
[10] Fast Exact Computation of the k Most Abundant Isotope Peaks with Layer-Ordered Heaps
Kreitzberg, Patrick
Pennington, Jake
Lucke, Kyle
Serang, Oliver
[J]. ANALYTICAL CHEMISTRY, 2020, 92 (15) : 10613 - 10619

← 1 2 →