Enumeration of PLCP-orientations of the 4-cube
Enumeration of PLCP-orientations of the 4-cube
复制标题
4 立方体 PLCP 方向的枚举
DOI：
10.1016/j.ejc.2015.03.010
复制
发表时间：
2015
影响因子：
1
通讯作者：
Lorenz Klaus and Hiroyuki Miyata
中科院分区：
文献类型：
--
作者：
Endo M;Iwamoto M;Sugawara M;Araki Y;Mori T;Shimizu K;Setsu N;Kobayashi E;Tanzawa Y;Nakatani F;Chuman H;Higashi T;Kawai A.;疋田理奈，東堀紀尚，福岡裕樹，宮本順，川元龍夫，森山啓司;Lorenz Klaus and Hiroyuki Miyata
线性互补问题（LCP）为线性规划、凸二次规划和双矩阵对策等问题提供了一种统一的解决方法。一般的LCP已知是NP-难的，但有一些有希望的结果表明，LCP与P-矩阵（PLCP）可能是多项式时间可解的。然而，没有多项式时间算法的PLCP已被发现，PLCP的计算复杂性仍然是开放的。简单主枢（SPP）算法，也称为Bard型算法，是PLCP多项式时间算法的候选者。1978年，Stickney和沃森将SPP算法解释为寻找n-立方体的唯一汇方向的汇的算法族。他们进行了3-立方体的出现方向的枚举，以下称为PLCP方向。本文给出了4-立方体的PLCP-定向的计数。通过构造有向拟阵、推广P-矩阵和对有向拟阵进行可实现性分类来实现计数。在计算实验中获得的一些见解以及。
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.
登录
查看更多内容
计算具有整数约束的二次最大化问题上限的连续方法
DOI：
10.1515/9781400862528.125
发表时间：
1992
期刊：
--
影响因子：
--
作者：
A. Kamath;N. Karmarkar
通讯作者：
N. Karmarkar
DOI：
10.1007/bfb0082792
发表时间：
1988
期刊：
--
影响因子：
--
作者：
N. Mnev
通讯作者：
N. Mnev
DOI：
10.1109/sfcs.2001.959931
发表时间：
2001-10
期刊：
Proceedings 2001 IEEE International Conference on Cluster Computing
影响因子：
--
作者：
Tibor Szabó;E. Welzl
通讯作者：
Tibor Szabó;E. Welzl
影响因子：
0.5
作者：
L. Finschi
通讯作者：
L. Finschi
可通过多项式有界旋转算法解决的线性互补问题
DOI：
--
发表时间：
1985
期刊：
影响因子：
--
作者：
J. Pang;R. Chandrasekaran
通讯作者：
R. Chandrasekaran