A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary
A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary
复制标题
一种近似混合判别式和混合体积的确定性算法以及组合推论
DOI：
10.1007/s00454-001-0083-2
复制
发表时间：
2002
影响因子：
0.8
通讯作者：
Alex Samorodnitsky
中科院分区：
文献类型：
--
作者：
L. Gurvits;Alex Samorodnitsky
我们提出了一个确定性的多项式时间算法，计算混合判别的n元组的半正定矩阵内的指数乘法因子。为此，我们扩展了双随机矩阵缩放的概念，一个更大的类的n -元组的半正定矩阵，并提供了一个多项式时间的算法，这种缩放。作为一个推论，我们得到一个确定性的多项式算法，计算混合体积的n个凸体在Rn内的误差，这只取决于尺寸。这回答了Dyer、Gritzmann和Hufnagel的一个问题。一个“附带好处”是Rado定理关于线性独立断面存在性的推广。
We present a deterministic polynomial-time algorithm that computes the mixed discriminant of an n -tuple of positive semidefinite matrices to within an exponential multiplicative factor. To this end we extend the notion of doubly stochastic matrix scaling to a larger class of n -tuples of positive semidefinite matrices, and provide a polynomial-time algorithm for this scaling. As a corollary, we obtain a deterministic polynomial algorithm that computes the mixed volume of n convex bodies in Rn to within an error which depends only on the dimension. This answers a question of Dyer, Gritzmann and Hufnagel. A ``side benefit'' is a generalization of Rado's theorem on the existence of a linearly independent transversal.