论文标题
半随机过程而无需更换
Semi-random process without replacement
论文作者
论文摘要
半随机过程涉及一个自适应决策者，其目标是在在线随机环境中实现一些预定的目标。我们介绍和研究半随机的多编码过程，该过程构成了Ben-Eliezer，Hefetz，Kronenberg，Parczyk，Shikhelman和Stojaković（2020）引入的过程的无替代变体。该过程从顶点集$ [n] $上的空图开始。对于每个积极的整数$ q $和$ 1 \ leq r \ leq n $，在$（（q-1）n+r）中，该过程的$ th youndremaker称为\ emph {builder}，提供了顶点，从随机均匀。然后，建筑商选择了一个额外的顶点（根据他选择的策略），并将其连接到$π_q（r）$。 对于几种天然图形属性，例如$ k $ - 连接性，最低度至少$ k $以及构建给定的跨度图（标记或未标记），我们确定典型的回合构建器需求，以构建具有所需属性的图形。在此过程中，我们介绍并分析了可能也具有独立兴趣的urn模型。
Semi-random processes involve an adaptive decision-maker, whose goal is to achieve some pre-determined objective in an online randomized environment. We introduce and study a semi-random multigraph process, which forms a no-replacement variant of the process that was introduced by Ben-Eliezer, Hefetz, Kronenberg, Parczyk, Shikhelman and Stojaković (2020). The process starts with an empty graph on the vertex set $[n]$. For every positive integers $q$ and $1\leq r\leq n$, in the $((q-1)n+r)$th round of the process, the decision-maker, called \emph{Builder}, is offered the vertex $π_q(r)$, where $π_1, π_2, \ldots$ is a sequence of permutations in $S_n$, chosen independently and uniformly at random. Builder then chooses an additional vertex (according to a strategy of his choice) and connects it by an edge to $π_q(r)$. For several natural graph properties, such as $k$-connectivity, minimum degree at least $k$, and building a given spanning graph (labeled or unlabeled), we determine the typical number of rounds Builder needs in order to construct a graph having the desired property. Along the way we introduce and analyze an urn model which may also have independent interest.
