2013/09/27 by Klaus, Lorenz, Miyata, Hiroyuki
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1309.7225
openalex publication_date 2013/09/27 · openalex created_date 2017/01/06 · openalex updated_date 2026/07/28
The linear complementarity problem (LCP) provides a unified approach to many problems such as linear programs, convex quadratic programs, and bimatrix games. The general LCP is known to be NP-hard, but there are some promising results that suggest the possibility that the LCP with a P-matrix (PLCP) may be polynomial-time solvable. However, no polynomial-time algorithm for the PLCP has been found yet and the computational complexity of the PLCP remains open. Simple principal pivoting (SPP) algorithms, also known as Bard-type algorithms, are candidates for polynomial-time algorithms for the PLCP. In 1978, Stickney and Watson interpreted SPP algorithms as a family of algorithms that seek the sink of unique-sink orientations of n-cubes. They performed the enumeration of the arising orientations of the 3-cube, hereafter called PLCP-orientations. In this paper, we present the enumeration of PLCP-orientations of the 4-cube.The enumeration is done via construction of oriented matroids generalizing P-matrices and realizability classification of oriented matroids.Some insights obtained in the computational experiments are presented as well.