A parallel algorithm for solving the linear complementarity problem |
| |
Authors: | A T Phillips J B Rosen |
| |
Institution: | (1) Department of Computer Science, University of Minnesota, 55455 Minneapolis, MN, U.S.A |
| |
Abstract: | The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row linear programming problem is considered. Based on this, an algorithm for solving the Linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP's where thenxn dense matrixM has no special properties (hence, the problem is NP-hard). based on these results, an average time performance ofO(n
4) is observed. |
| |
Keywords: | Combinatorial Optimization Linear Complementarity Problem Mathematical Programming Multitasking Parallel Processing |
本文献已被 SpringerLink 等数据库收录! |
|