Efficient median finding and its application to two-variable linear programming on mesh-connected computers with multiple broadcasting

[[abstract]]©1992 Elsevier-The paper considers 2-dimensional mesh-connected computers with multiple broadcasting (2-MCCMBs). A 2-MCCMB is constructed by augmenting a 2-dimensional mesh-connected computer with broadcasting features in each row and each column. One property of the modified mesh is that rectangular 2-MCCMBs, instead of square ones, are the best form for several algorithms. For the median problem of N numbers, a previous algorithm with time complexity O(N1/6(log N)2/3) was developed on an N1/2×N1/2 2-MCCMB. The paper shows that the time complexity can be reduced to O(N1/8 log N) if an N5/8×N3/8 rectangular 2-MCCMB is used. Using the above result, it further develops algorithms for two-variable linear programming on an N5/8×N3/8 2-MCCMB, where N is the number of constraints. In addition, to achieve better performance on the N5/8×N3/8 2-MCCMB, it further modifies a previous prune-and-search strategy for solving the problem and eventually obtains a parallel algorithm with O(N1/8 log N) time on an N5/8×N3/8 2-MCCMB.[[department]]資訊工程學