Pivoting in Linear Complementarity: Two Polynomial-Time Cases

Details Pivoting in Linear Complementarity: Two Polynomial-Time Cases Pivoting in Linear Complementarity: Two Polynomial-Time Cases

2008-07-08

arxiv.org/abs/0807.1249v2

Discrete Comput. Geom., 42(2), pp. 187-205, 2009

Mathematics

Optimization and Control

20 pages, v2: restructured and shortened, implemented referees' suggestions

Scientific paper

10.1007/s00454-009-9182-2

We study the behavior of simple principal pivoting methods for the P-matrix linear complementarity problem (P-LCP). We solve an open problem of Morris by showing that Murty's least-index pivot rule (under any fixed index order) leads to a quadratic number of iterations on Morris's highly cyclic P-LCP examples. We then show that on K-matrix LCP instances, all pivot rules require only a linear number of iterations. As the main tool, we employ unique-sink orientations of cubes, a useful combinatorial abstraction of the P-LCP.

Affiliated with

Also associated with

No associations

Rating

Pivoting in Linear Complementarity: Two Polynomial-Time Cases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pivoting in Linear Complementarity: Two Polynomial-Time Cases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pivoting in Linear Complementarity: Two Polynomial-Time Cases will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-268824