| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-10-31 16:10 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて 青島良一（東大）・○宮田洋行・森山園子（東北大）  COMP2012-41 |
|
| 抄録 | （和） | 今日、線形計画問題が強多項式時間で解けるかは一大未解決問題であり、特に単体法が適当なピボット規則のもと、強多項式時間アルゴリズムになりうるのかが大きく注目されている。単体法の解析において、単体法の可能な振る舞いを記述した線形計画グラフの組合せ的性質を解明することは、その意味で非常に重要である。 本論文では、まず線形計画向き付けが完全に組合せ的に特徴づけられる多面体クラスについて知られている結果を振り返った後、頂点数d+2のd次元多面体の線形計画向き付けを考察する。そのような多面体の線形計画向き付けは、Mihalisinにより組合せ的な特徴づけが得られていたが、本論文では、別の特徴づけとして、2009年にAvisとMoriyamaにより提案されたシェリング性でも特徴づけられることを示す。 |
| （英） | Today, it is one of the most outstanding problems in combinatorial optimization to decide whether linear programs can be solved in strongly polynomial time. In particular, the question whether the simplex method with a suitable pivot rule can be a strongly polynomial time algorithm for linear programs is gathering large attention. In this context, it is important to investigate combinatorial properties of linear program digraphs, which describe all possible behaviors of the simplex method. In this paper, we consider classes of polytopes whose LP orientations can be characterized by the shelling property, a combinatorial property of linear program digraphs proposed by Avis and Moriyama (2009). We first review existing results on combinaotorial characterizations of LP orientations of polytopes in some restricted classes and then study LP orientations of $d$-polytopes with $d+2$ vertices, which were characeterized in a purely combinatorial way by Mihalisin. We prove that they can also be characterized by the shelling property. |
|
| キーワード | （和） | 多面体 / 線形計画問題 / シェリング / / / / / |
| （英） | polytope / linear programming / shelling / / / / / | |
| 文献情報 | 信学技報, vol. 112, no. 272, COMP2012-41, pp. 45-51, 2012年10月. | |
| 資料番号 | COMP2012-41 | |
| 発行日 | 2012-10-24 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2012-41 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2012-10-31 - 2012-10-31 |
| 開催地（和） | 東北大学 |
| 開催地（英） | Tohoku University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2012-10-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて |
| サブタイトル（和） | |
| タイトル（英） | On classes of polytopes whose LP orientations can be characterized by the shelling property |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 多面体 / polytope |
| キーワード(2)（和/英） | 線形計画問題 / linear programming |
| キーワード(3)（和/英） | シェリング / shelling |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 青島 良一 / Yoshikazu Aoshima / アオシマ ヨシカズ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) University of Tokyo (略称： Univ. of Tokyo) |
| 第2著者 氏名（和/英/ヨミ） | 宮田 洋行 / Hiroyuki Miyata / ミヤタ ヒロユキ |
| 第2著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 森山 園子 / Sonoko Moriyama / モリヤマ ソノコ |
| 第3著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 講演者 | 第2著者 |
| 発表日時 | 2012-10-31 16:10:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2012-41 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.272 |
| ページ範囲 | pp.45-51 |
| ページ数 | 7 |
| 発行日 | 2012-10-24 (COMP) |
[研究会発表申込システムのトップページに戻る]