On the computational complexity of piecewise-linear homotopy algorithms |
| |
Authors: | Michael J Todd |
| |
Institution: | (1) School of Operations Research and Industrial Engineering, Cornell University, 14853 Ithaca, NY, USA;(2) University of Cambridge, Cambridge, England |
| |
Abstract: | We show that piecewise-linear homotopy algorithms may take a number of steps that grows exponentially with the dimension when solving a system of linear equations whose solution lies close to the starting point. Our examples are based on an example of Murty exhibiting exponential growth for Lemke's algorithm for the linear complementarity problem.This research was supported in part by NSF grant ECS-7921279 and by a Guggenheim Fellowship. |
| |
Keywords: | Piecewise-linear Homotopy Algorithms Computational Complexity Exponential Growth Linear Complementarity Problem |
本文献已被 SpringerLink 等数据库收录! |