错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A quick estimate for the volume of a polyhedron

  • Alexander Barvinok,
  • Mark Rudelson

摘要

Let P be a bounded polyhedron defined as the intersection of the non-negative orthant ℝ + n and an affine subspace of codimension m in ℝn. We show that a simple and computationally efficient formula approximates the volume of P within a factor of γm, where γ > 0 is an absolute constant. The formula provides the best known estimate for the volume of transportation polytopes from a wide family.