Peer Review #2 of "Selection on X1 + X2 + ⋯ + Xm via Cartesian product trees (v0.1)"
2021
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 selection on \(X_1 + X_2 + \cdots X_m\)X_1+X_2+\cdots+X_m\) in \(X_1 + X_2 + \cdots X_m\)o(n\cdot m + k\cdot m)\), where \(X_1 + X_2 + \cdots X_m\)X_i\) have length \(X_1 + X_2 + \cdots X_m\)n\).Here, that \(X_1 + X_2 + \cdots X_m\)o(n\cdot m + k\cdot m)\) algorithm is combined with a novel, optimal LOH-based algorithm for selection on \(X_1 + X_2 + \cdots X_m\)X+Y\) (without a soft heap).Performance of algorithms for selection on \(X_1 + X_2 + \cdots X_m\)X_1+X_2+\cdots+X_m\) are compared empirically, demonstrating the benefit of the algorithm proposed here.