Observations on a Class of Nasty Linear Complementarity Problems.
Abstract
Earlier papers by Murty (16) and Fathi (7) have exhibited classes of linear complementarity problems for which the computational effort (number of pivot steps) required to solve them by Lemke's algorithm (13) or Murty's algorithm (15) grows exponentially with the problem size (number of variables). In this paper we consider the sequences of complementary bases that arise as these problems are solved by the aforementioned algorithms. There is a natural correspondence between these bases and binary n-vectors through which the basis sequences can be identified with particular hamiltonian paths on the unit n-cube and with the binary Gray code representations of the integers from 0 to 2 to the n minus 1. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1978
- Accession Number
- ADA068472
Entities
People
- Richard Cottle
Organizations
- Stanford University