论文标题
在矩形的相关间隙上
On the Correlation Gap of Matroids
论文作者
论文摘要
设置函数可以通过各种方式扩展到单位立方体。相关差距测量两个自然扩展之间的比率。在一系列近似算法和机理设计设置中，该数量已被确定为性能保证。众所周知，单调下一个功能的相关差距至少为$ 1-1/e $，这对于简单的Matroid Rank函数来说很紧。 我们启动了针对矩阵级函数的相关差距的细粒研究。特别是，我们在相关差距上提出了一个改进的下限，如由矩阵的等级和周长所参数。我们还表明，对于任何矩阵，其加权矩形函数的相关差距在均匀的权重下最小化。这种改进的下限在Matroid约束，机理设计和争夺分辨率方案下具有直接应用，用于下次化最大化。
A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is at least $1-1/e$, and this is tight for simple matroid rank functions. We initiate a fine-grained study of the correlation gap of matroid rank functions. In particular, we present an improved lower bound on the correlation gap as parametrized by the rank and girth of the matroid. We also show that for any matroid, the correlation gap of its weighted matroid rank function is minimized under uniform weights. Such improved lower bounds have direct applications for submodular maximization under matroid constraints, mechanism design, and contention resolution schemes.
