Pivoting in Linear Complementarity: Two Polynomial-Time Cases

Foniok, J, Fukuda, K, Gaertner, B and Luethi, H-J (2009) Pivoting in Linear Complementarity: Two Polynomial-Time Cases. Discrete & Computational Geometry, 42. ISSN 0179-5376

Preview

Available under License In Copyright.
Download (254kB) | Preview

Abstract

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.

Item Type:	Article
Peer-reviewed:	No
Date Deposited:	11 Mar 2016 14:36
Publisher:	Springer-Verlag
Additional Information:	This is an Author Final Copy of a paper accepted for publication in Discrete & Computational Geometry, published by and copyright Springer-Verlag.
Divisions:
URI:	https://e-space.mmu.ac.uk/id/eprint/601193
DOI:	https://doi.org/10.1007/s00454-009-9182-2
ISSN	0179-5376

Impact and Reach

Statistics

DownloadsShow export options

Activity Overview

6 month trend

215Downloads

6 month trend

299Hits

Additional statistics for this dataset are available via IRStats2.

Altmetric

Repository staff only

Edit record