论文标题
部分可观测时空混沌系统的无模型预测
An Improved Lower Bound for Matroid Intersection Prophet Inequalities
论文作者
论文摘要
我们认为先知不平等受到可行性限制，这是$ Q $ Matroids的交集。最著名的算法达到了$θ（q）$ - 近似，即使仅限于$ q $ partition Matroids的交集，并且与I.I.D. 〜Bernoulli随机变量。先前最著名的下限是$θ（\ sqrt {q}）$，这是由于[Kleinberg-Weinberg Stoc 2012]的简单构造（使用I.I.D.〜Bernoulli随机变量，并将构造作为分区矩阵的相互作用）。 我们通过编写[Kleinberg-Weinberg STOC 2012]的构造来建立$ q^{1/2+ω（1/\ log \ log q）} $的改进的下限。我们使用[Alon-Alweiss Europe of Combinatorics 2020]中开发的最新技术，通过使用$ p^p $ dissiques of Size $ p $的$ p^p $分离集团的产品维度的改进上限来实现这一目标。
We consider prophet inequalities subject to feasibility constraints that are the intersection of $q$ matroids. The best-known algorithms achieve a $Θ(q)$-approximation, even when restricted to instances that are the intersection of $q$ partition matroids, and with i.i.d.~Bernoulli random variables. The previous best-known lower bound is $Θ(\sqrt{q})$ due to a simple construction of [Kleinberg-Weinberg STOC 2012] (which uses i.i.d.~Bernoulli random variables, and writes the construction as the intersection of partition matroids). We establish an improved lower bound of $q^{1/2+Ω(1/\log \log q)}$ by writing the construction of [Kleinberg-Weinberg STOC 2012] as the intersection of asymptotically fewer partition matroids. We accomplish this via an improved upper bound on the product dimension of a graph with $p^p$ disjoint cliques of size $p$, using recent techniques developed in [Alon-Alweiss European Journal of Combinatorics 2020].
