Enumeration of PLCP-orientations of the 4-cube

DOI10.1016/J.EJC.2015.03.010zbMATH Open1319.05014arXiv1309.7225OpenAlexW2063037623MaRDI QIDQ491752FDOQ491752

Authors: Lorenz Klaus, Hiroyuki Miyata 

Publication date: 19 August 2015

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

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.

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

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

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)

Cites Work

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

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)