2020/08/16 by Patrick Kreitzberg, Kyle Lucke, Kreitzberg, Patrick +5
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.2008.07023
arxiv created 2020/08/16 · openalex publication_date 2020/08/16 · arxiv updated 2020/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on X+Y, based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of X+Y selections was proposed to perform k-selection on X1+X2+⋯+Xm in o(n⋅ m + k⋅ m), where Xi have length n. Here, that o(n⋅ m + k⋅ m) algorithm is combined with a novel, optimal LOH-based algorithm for selection on X+Y (without a soft heap). Performance of algorithms for selection on X1+X2+⋯+Xm are compared empirically, demonstrating the benefit of the algorithm proposed here.