Two parallel algorithms for finding all minimal maximum subsequences

摘要

A minimal maximum subsequence is a minimal subsequence with maximum cumulative sum. We present two parallel algorithms that find all successive minimal maximum subsequences: one on the parallel random-access model in logarithmic time with linear work, and the other with overlapping domain decomposition on cluster systems. We confirm the efficacy and efficiency of the latter algorithm for random sequences via: (1) an application of random-walk theory that derives an approximate probabilistic length upper bound for overlapping subsequences — thus facilitating concurrent/independent computations of all minimal maximum subsequences in hosting processors, and (2) an empirical study with normally-distributed random sequences.