講演抄録/キーワード |
講演名 |
2012-12-10 16:40
4次元超立方体上のPLCP向き付けの列挙 福田公明・Lorenz Klaus(チューリッヒ工科大)・○宮田洋行(東北大) COMP2012-50 |
抄録 |
(和) |
線形相補性問題(LCP)は線形計画問題、凸二次計画、双行列ゲームなど多くの問題に統一的アプローチを与える重要な問題である。一般にLCPはNP困難であるが、係数行列が$P$行列の場合(PLCP)はいくつも良い性質を持ち、多項式時間可解である可能性を示唆する結果がある。一方、依然としてPLCPの多項式時間アルゴリズムは見つかっておらず、計算複雑度は不明なままである。多項式時間アルゴリズムの候補として、Bard-typeアルゴリズムがあるが、1978年にStickneyとWatsonはBard-typeアルゴリズムを、超立方体グラフに向きをつけ(PLCP向き付け)、そのシンクを探すアルゴリズムとして定式化し、さらに3次元超立方体上でPLCP向き付けを列挙した。
本論文では、有向マトロイドの実現可能性問題を通じて、4次元超立方体上のPLCP向き付けを列挙する。また、計算機実験により得られた種々の知見を紹介する。 |
(英) |
The linear complementarity problem (LCP) is an important problem, which provides unified approaches to many problems such as linear programs, convex quadratic problems and bimatrix games. In general, the LCP is known to be NP-hard, but there are some positive results that implies the possibility that the LCP whose coefficient matrix is a $P$-matrix (PLCP) might be polynomial-time solvable. However, no polynomial-time algorithm for the PLCP has been found yet and the computational complexity of the PLCP remains unknown. Bard-type algorithms are ones of candidates for polynomial-time algorithms for the PLCP. In 1978, Stickney and Watson interpreted Bard-type algorithms as algorithms to find a sink of a cube graph with a certain orientation, called a PLCP-orientations, and performed the enumeration of PLCP-orientaions on the $3$-cube.
In this paper, we perform the enumeration of PLCP-orientations on the $4$-cube via the realizability problem of oriented matroids. We also present some insights obtained in the computational experiments. |
キーワード |
(和) |
線形相補性問題 / 有向マトロイド / 実現可能性問題 / 唯一シンク向き付け / / / / |
(英) |
the linear complementarity problem / oriented matroids / the realizability problem / unique sink orientations / / / / |
文献情報 |
信学技報, vol. 112, no. 340, COMP2012-50, pp. 41-48, 2012年12月. |
資料番号 |
COMP2012-50 |
発行日 |
2012-12-03 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2012-50 |