The lexicographically first maximal 3 sum (LFM3S) problem is known as one of P-complete problems, which are hard to be parallelized. In this paper, we present two parallel algorithms for computing LFM3S on the BSP model. The first algorithm runs in O(n2/p + n log n + np) computation time and O(n(gp + L/p)) communication time, when n is the input size, p is the number of processors, and g, L are parameters which represent communication cost on the BSP model. The second algorithm runs in O(n2/p + n log n + nbp) computation time and O(n(gbp + L/bp)) communication time. The two algorithms are cost optimal for p ≤ √(n/g) and p ≤ √(n/gb), respectively. In addition, we implement these algorithms on a PC cluster, and show that these algorithms achieve practical speedup.
