论文标题
在在线搜索图中最大化预期的组件数量
Maximizing the expected number of components in an online search of a graph
论文作者
论文摘要
考虑以下最佳停止问题。图$ g $的顶点以随机顺序向选择器一一揭示。他的目标是在$ t $的时间停止此过程，以最大化图形$ \ tilde {g} _t $中预期的连接组件数量，这是由当前显示的顶点引起的。选择器提前知道$ g $，但是游戏的不同版本根据他获得的信息约为$ \ tilde {g} _t $。我们表明，当$ g $具有$ n $顶点和最高订单$ o（\ sqrt {n}）$的最高程度时，则$ \ tilde {g} _t $的组件数量集中在其平均值上，这意味着播放最佳策略不会通过接收更多信息来获得更多信息，从而获得$ \ tilde的更多信息来受益。 M.Lasoń先前获得了类似性质的结果，因为$ g $为$ k $ -tree（对于常数$ k $）。我们还考虑了$ g $是正方形，三角形或六角形晶格的特定情况，表明最佳选择器会获得$ CN $组件，并且我们在每种情况下计算出错误小于$ 0.005 $的$ c $。
The following optimal stopping problem is considered. The vertices of a graph $G$ are revealed one by one, in a random order, to a selector. He aims to stop this process at a time $t$ that maximizes the expected number of connected components in the graph $\tilde{G}_t$, induced by the currently revealed vertices. The selector knows $G$ in advance, but different versions of the game are considered depending on the information that he gets about $\tilde{G}_t$. We show that when $G$ has $N$ vertices and maximum degree of order $o(\sqrt{N})$, then the number of components of $\tilde{G}_t$ is concentrated around its mean, which implies that playing the optimal strategy the selector does not benefit much by receiving more information about $\tilde{G}_t$. Results of similar nature were previously obtained by M. Lasoń for the case where $G$ is a $k$-tree (for constant $k$). We also consider the particular cases where $G$ is a square, triangular or hexagonal lattice, showing that an optimal selector gains $cN$ components and we compute $c$ with an error less than $0.005$ in each case.
