The Two-Glance Deadline Problem: Limited Attention, Deadline Filtering, and Parking Functions

How much is lost when a deadline policy can inspect only a few of the items awaiting service? We introduce and analyze the d-glance deadline process: a batch of n items has independent uniform deadlines in (0,1) and n equally spaced service opportunities. At each opportunity, a fresh uniform sample of up to d surviving items is inspected and its most urgent item is served. Every item left unserved at its deadline is lost. For each fixed d, the served fraction converges to s_d = 1 - exp{-∫_0^1 dx/(1-x+x^d)}, with exponentially small probabilities of fixed-size deviations. Two observations give s_2 = 1 - exp{-2π/(3√3)} ≈ 0.701564, compared with s_1 = 1-e^{-1}. A three-term expansion of the extinction integral yields a lost fraction asymptotic to W(d)/d as d tends to infinity. Full-information service provides a classical parking-function benchmark, with losses of order √n. Even conditioning the deadline vector to be completely feasible leaves the sampled policy's limit s_d unchanged. We also represent the process as a minimum-card permutation followed by an adaptive deadline scan. Exact finite-state generating functions and, for d=2, a rooted-tree description count the sampling histories that meet every deadline. Their first total counts are 1, 3, 39, 1338, 95280, ... . Keywords добавь по одному: