论文标题
在流模型中，单调下函数最大化的单调函数最大化的性能最大化
Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
论文作者
论文摘要
在各种约束下，最大化单调下调函数是经典且深入研究的问题。但是，在单频道流媒体模型中，其中元素一个一个一个一个，并且算法只能存储一小部分输入元素，即使文献中已经提出了几种近似算法，我们的知识存在很大的差距。 在这项工作中，我们介绍了单个pass流模型中的$ 1- \ frac {1} {e} $击败$ 1- \ frac {e} $的近似值的第一个下限。令$ n $为流中的元素数量。然后，我们证明具有近似值$ \ frac {2} {2+ \ sqrt {2}}}+\ varepsilon $需要$ω\ left（\ frac {n} $ k $ k $ k的$ k $ k $ k $ k $ k $ k $ k $ k $ k $ k的任何（随机）流算法的任何（随机）流算法近似值$ \ frac {2} {2+\ sqrt {2}}+\ varepsilon $输出集的尺寸限制。我们还证明，具有近似值比$ \ frac {k} {k} {2k-1}+\ varepsilon $的任何（随机）流算法需要$ω\ left（\ frac {n} {n} {k} {k} {k} {k} {k} {k} {k} {k} {k} {k} { 此外，当我们只有一个弱的甲骨文时，我们只能在可行的集合上评估函数值时给出流算法。具体而言，我们显示了针对基数和具有近似值比的基质限制的弱轨道流算法$ \ frac {k} {2k-1} $和$ \ frac {1} {2} {2} $，其空间复杂性在$ k $中是$ k $，但独立于$ n $。前者与弱Oracle模型中基数约束的已知无Xibibibibibibibibibibibibibibibibibibibibibility结果匹配。 对于矩阵约束，后一个几乎与我们的下限$ \ frac {k} {2k-1} $相匹配，该约束几乎可以通过流式算法获得空间复杂性独立于$ n $而获得的矩阵约束的近似值。
Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is much gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat $1-\frac{1}{e}$ in the single-pass streaming model. Let $n$ be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio $\frac{2}{2+\sqrt{2}}+\varepsilon$ requires $Ω\left(\frac{n}{K^2}\right)$ space for any $\varepsilon>0$, where $K$ is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio $\frac{K}{2K-1}+\varepsilon$ requires $Ω\left(\frac{n}{K}\right)$ space for any $\varepsilon>0$, where $K$ is the rank of the given matroid. In addition, we give streaming algorithms when we only have a weak oracle with which we can only evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios $\frac{K}{2K-1}$ and $\frac{1}{2}$, respectively, whose space complexity is exponential in $K$ but is independent of $n$. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of $\frac{K}{2K-1}$ for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of $n$.
