| 講演名 | 2012-10-31 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて 青島 良一, 宮田 洋行, 森山 園子, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 今日、線形計画問題が強多項式時間で解けるかは一大未解決問題であり、特に単体法が適当なピボット規則のもと、強多項式時間アルゴリズムになりうるのかが大きく注目されている。単体法の解析において、単体法の可能な振る舞いを記述した線形計画グラフの組合せ的性質を解明することは、その意味で非常に重要である。本論文では、まず線形計画向き付けが完全に組合せ的に特徴づけられる多面体クラスについて知られている結果を振り返った後、頂点数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. |
| キーワード(和) | 線形計画問題 / シェリング / 多面体 |
| キーワード(英) | Linear programming / shelling / polytope |
| 資料番号 | COMP2012-41 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2012/10/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて |
| サブタイトル（和） | |
| タイトル（英） | On classes of polytopes whose LP orientations can be characterized by the shelling property |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 線形計画問題 / Linear programming |
| キーワード(2)（和/英） | シェリング / shelling |
| キーワード(3)（和/英） | 多面体 / polytope |
| 第 1 著者 氏名（和/英） | 青島 良一 / Yoshikazu AOSHIMA |
| 第 1 著者 所属（和/英） | 東京大学大学院情報理工学系研究科コンピュータ科学専攻 Department of Computer Science, Graduate School of Information and Technology, the University of Tokyo |
| 第 2 著者 氏名（和/英） | 宮田 洋行 / Hiroyuki MIYATA |
| 第 2 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 3 著者 氏名（和/英） | 森山 園子 / Sonoko MORIYAMA |
| 第 3 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 発表年月日 | 2012-10-31 |
| 資料番号 | COMP2012-41 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 272 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |