| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2012-12-10 - 2012-12-10 |
| 開催地（和） | 九州大学 |
| 開催地（英） | Kyushu University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2012-12-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 4次元超立方体上のPLCP向き付けの列挙 |
| サブタイトル（和） | |
| タイトル（英） | Enumeration of PLCP-orientations on the 4-cube |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 線形相補性問題 / the linear complementarity problem |
| キーワード(2)（和/英） | 有向マトロイド / oriented matroids |
| キーワード(3)（和/英） | 実現可能性問題 / the realizability problem |
| キーワード(4)（和/英） | 唯一シンク向き付け / unique sink orientations |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 福田 公明 / Komei Fukuda / フクダ コウメイ |
| 第1著者 所属（和/英） | チューリッヒ工科大学 (略称： チューリッヒ工科大) Swiss Federal Institute of Technology Zurich (略称： ETH Zurich) |
| 第2著者 氏名（和/英/ヨミ） | Lorenz Klaus / Lorenz Klaus / |
| 第2著者 所属（和/英） | チューリッヒ工科大学 (略称： チューリッヒ工科大) Swiss Federal Institute of Technology Zurich (略称： ETH Zurich) |
| 第3著者 氏名（和/英/ヨミ） | 宮田 洋行 / Hiroyuki Miyata / ミヤタ ヒロユキ |
| 第3著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 講演者 | 第3著者 |
| 発表日時 | 2012-12-10 16:40:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2012-50 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.340 |
| ページ範囲 | pp.41-48 |
| ページ数 | 8 |
| 発行日 | 2012-12-03 (COMP) |
[研究会発表申込システムのトップページに戻る]