アンドウ エイ
ANDO Ei
安藤 映 所属 専修大学 ネットワーク情報学部 職種 准教授 |
|
言語種別 | 英語 |
発行・発表の年月 | 2019/04 |
形態種別 | 研究論文(学術雑誌) |
査読 | 査読あり |
標題 | The Volume of a Crosspolytope Truncated by a Halfspace |
執筆形態 | 共著 |
掲載誌名 | Lecture Notes in Computer Science, Springer |
掲載区分 | 国外 |
巻・号・頁 | 11436,pp.13-27 |
総ページ数 | 15 |
著者・共著者 | Ei Ando, Shoichi Tsuchiya |
概要 | In this paper, we consider the computation of the volume
of an n-dimensional crosspolytope truncated by a halfspace. Since a crosspolytope has exponentially many facets, we cannot efficiently compute the volume by dividing the truncated crosspolytope into simplices. We show an O(n^6) time algorithm for the computation of the volume. This makes a contrast to the 0−1 knapsack polytope, whose volume is #P-hard to compute. The paper is interested in the computation of the volume of the truncated crosspolytope because we conjecture the following question may have an affirmative answer: Does the existence of a polynomial time algorithm for the computation of the volume of a polytope K imply the same for K’s geometric dual? We give one example where the answer is yes. |
DOI | https://doi.org/10.1007/978-3-030-14812-6_2 |