A Full Feasible Dual Prevents Algorithmic Failure

For every pair of natural numbers $n=\mathrm{jobs}$ and $m=\mathrm{machines}$, and every instance $I$ consisting of a proof $0<m$, a load function $p:\mathrm{Fin}(n)\times\mathrm{Fin}(m)\to\mathbb R$, and proofs $0\le p(i,j)$ for all jobs $i$ and machines $j$, define $E_i=\{j\in\mathrm{Fin}(m)\mid p(i,j)\le1\}$ and $E=\{(i,j)\mid i\in\mathrm{Fin}(n),\,j\in E_i\}$. For every function $y:E\to\mathbb R$, if the hypothesis $h_y$ states all of the following—$y_{ij}\ge0$ for every $(i,j)\in E$; $\sum_{i:\,j\in E_i}p(i,j)y_{ij}\le1$ for every machine $j$; $\sum_{j\in E_i}y_{ij}\le1$ for every job $i$; and, additionally, $\sum_{j\in E_i}y_{ij}=1$ for every job $i$—then the deterministic run described below both has final failure marker $\mathrm{none}$ and satisfies $\forall i\in\mathrm{Fin}(n),\,\exists j\in\mathrm{Fin}(m)$ such that its final assignment entry for $i$ is $\mathrm{some}(j)$. The run starts with every machine weight equal to $1/(2m)$, every job assignment equal to $\mathrm{none}$, every job slack equal to $0$, every entry of its own internal rectangular dual array equal to $0$, and failure marker $\mathrm{none}$, and then recursively processes exactly the list $0,1,\ldots,n-1$ (formally, the first $n$ entries of that list). At an arrival $i$, if the current failure marker is already $\mathrm{some}(r)$, the entire state is left unchanged, so failure is absorbing. Otherwise it tests whether $E_i=\varnothing$ or whether some current machine weight $x_j$ satisfies $1<x_j$; if either condition holds, it changes only the failure marker to $\mathrm{some}(i)$. If neither holds, it deterministically asks for a machine $\ell\in E_i$ minimizing $p(i,\ell)x_\ell$, using the eligible machines sorted by their natural finite-index order to resolve the minimum deterministically; if this selection operation nevertheless returns no machine, it again changes only the failure marker to $\mathrm{some}(i)$, while if it returns $\ell$, with $p=p(i,\ell)$ and $x=x_\ell$ from the pre-update state, it replaces $x_\ell$ by $x(1+p/2)$, replaces the assignment of $i$ by $\mathrm{some}(\ell)$, replaces the slack of $i$ by $1-px$, replaces the internal dual entry at $(i,\ell)$ by $1$, leaves all other corresponding entries unchanged, and sets the failure marker to $\mathrm{none}$; the process’s emitted decision is the resulting assignment entry for $i$, and the next arrival receives the resulting state. The supplied certificate $y$ is not an input to these transitions. All displayed sums are finite, with an empty sum equal to $0$: consequently, if any job has $E_i=\varnothing$, its required unit-mass equation becomes $0=1$, so no $h_y$ exists and the theorem has no applicable hypothesis in that case; $m=0$ likewise supplies no instance because the instance binder requires $0<m$. By contrast, $n=0$ is included: then $E$ is empty, nonnegativity and all job-indexed conditions are vacuous, every machine constraint is $0\le1$, the run processes no arrivals and retains its initial $\mathrm{none}$ failure marker, and the assertion that every job is assigned is vacuous.