Enumeration of PLCP-orientations of the 4-cube

DOI10.1016/J.EJC.2015.03.010MaRDI QIDQ491752zbMATH OpenOpenAlexFDO

Authors Lorenz Klaus, Hiroyuki Miyata

Publication date 19 August 2015

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.7225

zbMATH Keywords

linear complementarity problemP-matrix

Mathematics Subject Classification ID

Quadratic programming (90C20) Linear programming (90C05) Directed graphs (digraphs), tournaments (05C20) Exact enumeration problems, generating functions (05A15) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Combinatorial aspects of matroids and geometric lattices (05B35) Linear inequalities of matrices (15A39)

Abstract: 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.

Recommendations

• Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
• Pivoting in linear complementarity: Two polynomial-time cases
• EP theorems and linear complementarity problems
• NP-completeness of the linear complementarity problem
• Two counterexamples on the polynomial solvability of the linear complementarity problem

Cites work

• scientific article; zbMATH DE number 3159112 (Why is no real title available?)
• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 3538668 (Why is no real title available?)
• scientific article; zbMATH DE number 3212891 (Why is no real title available?)
• scientific article; zbMATH DE number 2209726 (Why is no real title available?)
• A Partition Theorem for Euclidean n-Space
• A Probelm in Linear Inequalities
• A polynomial-time algorithm for a class of linear complementarity problems
• A unified approach to interior point algorithms for linear complementarity problems: A summary
• Bimatrix Equilibrium Points and Mathematical Programming
• Combinatorial characterizations of \(K\)-matrices
• Complementarity in Oriented Matroids
• Complementary pivot theory of mathematical programming
• Complete enumeration of small realizable oriented matroids
• Counting unique-sink orientations
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• Equilibrium Points of Bimatrix Games
• Generation of oriented matroids --- a graph theoretical approach
• Higher Bruhat orders and cyclic hyperplane arrangements
• LINEAR COMPLEMENTARITY AND ORIENTED MATROIDS
• LP-orientations of cubes and crosspolytopes
• Linear complementarity problems solvable by A single linear program
• Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
• Linear programming and unique sink orientations
• NP-completeness of the linear complementarity problem
• On the generation of oriented matroids
• On the number of solutions to the complementarity problem and spanning properties of complementary cones
• Oriented Matroids
• Pivoting in linear complementarity: Two polynomial-time cases
• Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
• Some generalizations of the criss-cross method for the linear complementarity problem of oriented matroids
• Unique sink orientations of grids

Cited in

(3)

• Realizability makes a difference: a complexity gap for sink-finding in USOs
• A Mihalisin-Klee theorem for fans
• On the Holt-Klee property for oriented matroid programming

This page was built for publication: Enumeration of PLCP-orientations of the 4-cube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491752)