Explicit Prefix Load Bound for Unrelated-Machine Scheduling

For every pair of natural numbers $n$ and $m$, every instance $I$ consisting of a load function $p:\operatorname{Fin}(n)\to\operatorname{Fin}(m)\to\mathbb R$ together with hypotheses $0<m$ and $0\le p_{i,j}$ for every job $i$ and machine $j$, and every $k\in\mathbb N$ satisfying $k\le n$, the declaration asserts that every $j\in\operatorname{Fin}(m)$ satisfies $\displaystyle \sum_{i\in\operatorname{Fin}(n)}\begin{cases}p_{i,j},&\text{if the assignment stored for }i\text{ after the prefix run is exactly }j,\\0,&\text{otherwise}\end{cases}\le \frac{\log(3m)}{\log(3/2)}$, where $\log$ is the real natural logarithm and the prefix run is the following deterministic state evolution on the first $k$ entries of the list $0,1,\ldots,n-1$: initially every machine has weight $1/(2m)$, every job has assignment $\mathsf{none}$ and slack $0$, every job–machine dual coordinate is $0$, and the failure marker is $\mathsf{none}$; at an arriving job $i$, if a prior failure marker is already present, the entire state is left unchanged, while otherwise the algorithm first declares failure at $i$—changing only the failure marker—if either the eligible set $\{j:p_{i,j}\le1\}$ is empty or some current machine weight is strictly greater than $1$; if neither condition holds, it selects from the eligible machines a minimizer of $p_{i,j}$ times the current weight of $j$, with the eligible machines sorted in their natural finite order before the deterministic argmin, and, for a selected machine $\ell$, writes assignment $i=\ell$, writes slack $1-p_{i,\ell}x_\ell$ using the old weight $x_\ell$, writes dual coordinate $(i,\ell)=1$, replaces $x_\ell$ by $x_\ell(1+p_{i,\ell}/2)$, leaves all other coordinates unchanged, and keeps the failure marker empty; the transition definition also contains a fallback that marks failure at $i$ if the machine-selection operation returns no machine, although after the empty-eligible-set test has failed the eligible set is nonempty. The overweight test occurs before the current update, so an update may first raise a weight above $1$ and this triggers failure only at a later arrival, if there is one. On any failure, all assignments already made remain in the retained state, the failing job receives no new assignment, and every later arrival in the requested prefix sees the absorbing failed state, so the displayed sum is still over all $n$ job indices but only assignments present in that retained state contribute. No success, all-jobs-assigned, primal-feasibility, or dual-feasibility hypothesis is imposed. The case $k=0$ is included and uses the initial state, giving an empty set of contributing assignments; $n=0$ is included and, because $k\le n$, forces $k=0$ and makes the sum over jobs empty; values $k>n$ are excluded by the stated hypothesis, so the taken list prefix has exactly $k$ arrivals; and although $m=0$ is among the outer natural-number values, no such instance can satisfy $0<m$, making that case vacuous (and leaving no machine index $j$), while every actual instance has at least one machine but may still have an arriving job with no eligible machine.