Computational complexity of Van der Heyden's variable dimension algorithm and Dantzig-Cottle's principal pivoting method for solving LCP's |
| |
Authors: | John R Birge Akli Gana |
| |
Institution: | 1. Department of Industrial and Operations Engineering, The University of Michigan, 48109, Ann Arbor, MI, USA
|
| |
Abstract: | We show that Van der Heyden's variable dimension algorithm and Dantzig and Cottle's principal pivoting method require 2n–1 pivot steps to solve a class of linear complementarity problems of ordern. Murty and Fathi have previously shown that the computational effort required to solve a linear complementarity problem of ordern by Lemke's complementary pivot algorithm or by Murty's Bard-type algorithm is not bounded above by a polynomial inn. Our study shows that the variable dimension algorithm and the principal pivoting method have similar worst case computational requirements. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|