Name
Title | ||
|---|---|---|
Efficient median finding and its application to two-variable linear programming on mesh-connected computers with multiple broadcasting |
Abstract | ||
|---|---|---|
This 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(N 1 6 ( log N) 2 3 ) was developed on an N 1 2 × N 1 2 2-MCCMB. This paper shows that the time complexity can be reduced to O(N 1 8 log N) if an N 5 8 × N 3 8 rectangular 2-MCCMB is used. Using the above result, we further develop algorithms for two-variable linear programming on an N 5 8 × N 3 8 2-MCCMB, where N is the number of constraints. In addition, to achieve better performance on the N 5 8 × N 3 8 2-MCCMB, we further modify a previous prune-and-search strategy for solving the problem and eventually obtain a parallel algorithm with O(N 1 8 log N) time on an N 5 8 × N 3 8 2-MCCMB. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1016/0743-7315(92)90061-Q | J. Parallel Distrib. Comput. |
Keywords | Field | DocType |
efficient median finding,linear programming,multiple broadcasting,mesh-connected computer,time complexity,parallel algorithm,linear program,2 dimensional | Broadcasting,Binary logarithm,Combinatorics,Parallel algorithm,Parallel computing,Linear programming,Time complexity,Mathematics,Distributed computing | Journal |
Volume | Issue | ISSN |
15 | 1 | Journal of Parallel and Distributed Computing |
Citations | PageRank | References |
21 | 0.82 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yen-Cheng Chen | 1 | 152 | 15.38 |
| Wen-Tsuen Chen | 2 | 1271 | 129.24 |
| guihai chen | 3 | 3537 | 317.28 |