アンドウ　エイ   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