论文标题
贪婪探索算法上的大偏差原理
Large Deviation Principle for the Greedy Exploration Algorithm over Erdös-Rényi Graphs
论文作者
论文摘要
当节点数量输入无穷大时，我们证明了在Erdös-rényi（ER）图上进行贪婪探索过程的大偏差原理。为了证明我们的主要结果，我们使用一般策略来研究Feng和Kurtz提出的大偏差，该过程基于非线性半群的收敛性。速率函数可以以封闭形式的公式表示，并且可以明确解决相关的优化问题，从而提供较大的偏差轨迹。另外，我们得出了该算法发现的最大独立集的大小的LDP，并分析了它超过最大独立集的已知边界的概率。我们还分析了这些结果与独立集合的景观复杂性与勘探动态之间的联系。
We prove a large deviation principle for a greedy exploration process on an Erdös-Rényi (ER) graph when the number of nodes goes to infinity. To prove our main result, we use the general strategy to study large deviations of processes proposed by Feng and Kurtz, based on the convergence of non-linear semigroups. The rate function can be expressed in a closed-form formula, and associated optimization problems can be solved explicitly, providing the large deviation trajectory. Also, we derive an LDP for the size of the maximum independent set discovered by such an algorithm and analyze the probability that it exceeds known bounds for the maximal independent set. We also analyze the link between these results and the landscape complexity of the independent set and the exploration dynamic.
