论文标题
韦伯斯特序列，分配问题和即时排序
Webster Sequences, Apportionment Problems, and Just-In-Time Sequencing
论文作者
论文摘要
Given a real number $α\in (0,1)$, we define the Webster sequence of density $α$ to be $W_α= (\lceil(n-1/2) / α\rceil)_{n\in\mathbb{N}}$, where $\lceil x \rceil$ is the ceiling function.众所周知，如果$α$和$β$与$α+β= 1 $不合理，则$w_α$和$w_β$ partition $ \ mathbb {n} $。另一方面，三部分分区的类似结果并不成立：$ \ mathbb {n} $的分区中不存在$w_α，w_β，w_γ$，$α，β，γ$不合理。在本文中，我们考虑了一个问题，即有多接近$ \ mathbb {n} $的三部分分区到具有规定密度$α，β，γ$的Webster序列中。我们表明，如果$α，β，γ$与$α+β+γ= 1 $是不合理的，则存在$ \ m athbb {n} $的分区中的$ \ mathbb {n} $分为$α，β，γ$的序列，其中一个序列是WebSter序列，而另一个elements则根据“ Webster sequence” sequerence seece seceence seece sequect celes sequect sequerence severs celes。两种有效的算法来构建此类分区。第一种算法将每个序列的$ n $ th元素输出为$ o（1）$时间，第二个算法将$ m $ th的正整数分配给$ o（1）$时间的序列。我们表明，在多个方面，结果最有可能。此外，我们将这些结果的应用描述为分配和最佳调度问题。
Given a real number $α\in (0,1)$, we define the Webster sequence of density $α$ to be $W_α= (\lceil(n-1/2) / α\rceil)_{n\in\mathbb{N}}$, where $\lceil x \rceil$ is the ceiling function. It is known that if $α$ and $β$ are irrational with $α+ β= 1$, then $W_α$ and $W_β$ partition $\mathbb{N}$. On the other hand, an analogous result for three-part partitions does not hold: There does not exist a partition of $\mathbb{N}$ into sequences $W_α, W_β, W_γ$ with $α, β, γ$ irrational. In this paper, we consider the question of how close one can come to a three-part partition of $\mathbb{N}$ into Webster sequences with prescribed densities $α, β, γ$. We show that if $α, β, γ$ are irrational with $α+ β+γ= 1$, there exists a partition of $\mathbb{N}$ into sequences of densities $α, β, γ$, in which one of the sequences is a Webster sequence and the other two are "almost" Webster sequences that are obtained from Webster sequences by perturbing some elements by at most 1. We also provide two efficient algorithms to construct such partitions. The first algorithm outputs the $n$th element of each sequence in $O(1)$ time and the second algorithm gives the assignment of the $m$th positive integer to a sequence in $O(1)$ time. We show that the results are best-possible in several respects. Moreover, we describe applications of these results to apportionment and optimal scheduling problems.
