论文标题
图中许多连接组件的最佳停止
Optimal stopping for many connected components in a graph
论文作者
论文摘要
我们研究了一个新的最佳停止问题：让$ g $是固定的图表，其$ n $顶点及时地在线，一个随机顺序在线上变得活跃。 $ g $的活动部分是由活动顶点引起的子图。找到一种停止算法，该算法最大化了$ g $的活动部分的预期连接组件的预期数。我们证明，如果$ g $是$ k $ -tree，则没有比“等待到$ \ frac {1} {1} {k+1} $ raction的渐近算法更好。连接组件的最大预期数量等于$$ \ left（\ frac {k^k} {（k+1）^{k+1}}}}+o（1）\ right）n。$$
We study a new optimal stopping problem: Let $G$ be a fixed graph with $n$ vertices which become active on-line in time, one by another, in a random order. The active part of $G$ is the subgraph induced by the active vertices. Find a stopping algorithm that maximizes the expected number of connected components of the active part of $G$. We prove that if $G$ is a $k$-tree, then there is no asymptotically better algorithm than `wait until $\frac{1}{k+1}$ fraction of vertices'. The maximum expected number of connected components equals to $$\left(\frac{k^k}{(k+1)^{k+1}}+o(1)\right)n.$$
