首页|Webster sequences, apportionment problems, and just-in-time sequencing
Webster sequences, apportionment problems, and just-in-time sequencing
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
Given a real number alpha is an element of (0,1), we define the Webster sequence of density alpha to be W-alpha=((inverted right perpendicular )(n-1/2)/alpha(inverted left perpendicular ))(n is an element of N), where (inverted right perpendicular) x (inverted left perpendicular ) is the ceiling function. It is known that if alpha and beta are irrational with alpha+beta=1, then W-alpha and W-beta partition N. On the other hand, an analogous result for three-part partitions does not hold: There does not exist a partition of N into sequences W-alpha,W-beta,W-gamma with alpha,beta,gamma irrational. In this paper, we consider the question of how close one can come to a three-part partition of N into Webster sequences with prescribed densities alpha,beta,gamma. We show that if alpha,beta,gamma are irrational with alpha+beta+gamma=1, there exists a partition of N into sequences of densities alpha,beta,gamma, 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 nth element of each sequence in O(1) time and the second algorithm gives the assignment of the mth 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. (C) 2021 Elsevier B.V. All rights reserved.
NSTL
Elsevier
