Log-concave polynomials, I: Entropy and a deterministic approximation algorithm for counting bases of matroids
Log-concave polynomials, I: Entropy and a deterministic approximation algorithm for counting bases of matroids
复制标题
对数凹多项式，I：熵和用于计算拟阵基数的确定性近似算法
DOI：
10.1215/00127094-2020-0091
复制
发表时间：
2018
影响因子：
2.5
通讯作者：
C. Vinzant
中科院分区：
文献类型：
--
作者：
Nima Anari;S. Gharan;C. Vinzant
我们给出了确定性的多项式时间$ 2^{o（r）} $ - 给定等级$ r $的基碱数量和任何两个等级$ r $ r $的共同基础的基础数量的近似算法。据我们所知，这是第一个适用于任意矩阵的非平凡确定性近似算法。基于Azar，Broder和Frieze [abf94]的下限，这几乎是甲骨文访问Matroid集合的最佳结果。
我们的结果中有两种主要成分：首先，我们建立在Adiprasito，Huh和Katz [ahk15]和Huh和Wang [HW17]的最新结果上。我们预计将来将从此连接中得出几种近似算法中的几个新应用程序。正式地，我们证明，任何矩阵的碱基的多元生成多项式都是log-concave作为正骨上方的函数。对于第二个成分，我们基于凸优化开发了一个近似计数的一般框架。该连接经过熵的亚加性。对于矩阵，我们证明熵的近似超级药物是通过依靠相应多项式的对数洞穴而保持的。
We give a deterministic polynomial time $2^{O(r)}$-approximation algorithm for the number of bases of a given matroid of rank $r$ and the number of common bases of any two matroids of rank $r$. To the best of our knowledge, this is the first nontrivial deterministic approximation algorithm that works for arbitrary matroids. Based on a lower bound of Azar, Broder, and Frieze [ABF94] this is almost the best possible result assuming oracle access to independent sets of the matroid.
There are two main ingredients in our result: For the first, we build upon recent results of Adiprasito, Huh, and Katz [AHK15] and Huh and Wang [HW17] on combinatorial hodge theory to derive a connection between matroids and log-concave polynomials. We expect that several new applications in approximation algorithms will be derived from this connection in future. Formally, we prove that the multivariate generating polynomial of the bases of any matroid is log-concave as a function over the positive orthant. For the second ingredient, we develop a general framework for approximate counting in discrete problems, based on convex optimization. The connection goes through subadditivity of the entropy. For matroids, we prove that an approximate superadditivity of the entropy holds by relying on the log-concavity of the corresponding polynomials.
影响因子：
4.9
作者：
Adiprasito, Karim;Huh, June;Katz, Eric
通讯作者：
Katz, Eric