Low-Dimensional Vectors with Density Bounded by 5/6 Are Pinwheel Schedulable

摘要

Given an n-dimensional integer vector v = (v_1, v_2,..., v_n) with 2 ≤ v_1 ≤ v_2 ≤ • • • ≤ v_n, a pinwheel schedule for v is referred to as an infinite symbol sequence S_1S_2S_3 • • •, which satisfies that S_1 ∈ {1,2,..., n}, νj ∈ Z and every i ∈ {1,2,..., n} occurs at least once in every v_i consecutive symbols S_j+_1S_(j+2) • • • S_(j+v_i),V_j ∈ Z. If v has a pinwheel schedule then v is called (pinwheel) schedulable. The density of v is defined as d(v) = ∑~n_(i=1) ~1/_(vi) Chan and Chin [4] made a conjecture that every vector v with d(v) ≤ 5/6 is schedulable. In this paper, we examine the conjecture from the point of view of low-dimensional vectors, including 3-, 4- and 5-dimensional ones. We first discover some simple but important properties of schedulable vectors, and then apply these properties to test whether or not a vector is schedulable. As a result, we prove that the maximum density guarantee for low-dimensional vectors is |, which partially support this conjecture.