Answer: Yes: a uniformly efficiently computable online policy family satisfies the stated asymptotic approximation guarantee.
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe online-competitive analyses for SAMP and SAMP-S are both tight (i.e., the ratios presented above are the best ones they can ever achieve). Also, no algorithm can achieve an online-competitive ratio better than √ 3 −1 ∼ 0.732 even for homogeneous groups. We test our model and algorithms on publicly available COVID-19 vaccination datasets maintained by the Minnesota Department of Health.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite bipartite graph \((I,J,E)\), arrival rates \(\lambda_j\), supply masses \(b_i\), and singleton groups with targets \(\mu_j>0\), let type \(j\) arrive as a deterministic mass flow of rate \(\lambda_j\) over \([0,1]\). Each arriving mass unit must be assigned immediately and irrevocably to a feasible supplier or rejected, subject to supplier capacities. What is the best worst-case competitive ratio of causal fluid policies against the clairvoyant fluid optimum for maximizing \(\min_{j\in J} X_j/(\Lambda\mu_j)\), where \(X_j\) is the mass served and \(\Lambda=\sum_j\lambda_j\)?
A society is given by its support: the list of \(\tau=|J|\) demand types with positive binary-rational masses \(\nu_j\), where \(\sum_j\nu_j=1\); \(\tau\) is the support size, not the number of possible types.
The remaining input comprises a nonempty supply set \(I\), \(m=|I|\), a compatibility graph \(E\subseteq I\times J\), positive binary-rational capacities \(c_i\), and an explicitly listed nonempty collection \(\mathcal G\) of nonempty, possibly overlapping subsets of \(J\), with binary-rational targets \(\mu_g\in(0,1)\). Targets need not sum to one. Let \(L\) be the total input bit length and \(k=|\mathcal G|\).
For each admissible integer \(N\ge1\), meaning \(Nc_i\in\mathbb Z_{>0}\) for every \(i\), independent homogeneous Poisson processes generate type-\(j\) requests at rate \(N\nu_j\) on \([0,1]\). Each request has mass \(1/N\); serving it consumes one of the \(Nc_i\) slots at a compatible supply type.
An online policy knows the input and \(N\), and immediately and irrevocably rejects each arrival or assigns it wholly to one compatible supply type with a remaining slot; randomization is allowed. Set \(M_g=N^{-1}\sum_{j\in g}X_j\), where \(X_j\) counts served type-\(j\) requests, and \(V_N=\min_{g\in\mathcal G}\mathbb E[M_g]/\mu_g\), with expectations over arrivals and policy randomness.
Define \(\mathrm{OPT}_N\) as the supremum of this same value over feasible randomized policies allowed to observe the entire arrival sequence before allocating. The minimum remains outside the expectations.
Efficiency means polynomial preprocessing and expected computation per arrival in \(m,\tau,k,L,\log N\).
Does there exist a uniformly efficiently computable online policy family such that, for every fixed input and every \(\epsilon>0\), some \(N_0\) satisfies \(V_N\ge(1-\epsilon)\mathrm{OPT}_N\) for every admissible \(N\ge N_0\)?
For discrete requests, Xu and Xu establish an efficient policy with competitive ratio at least \(\max\{1-1/e,1-(2\pi b)^{-1/2}\}\), where \(b\) is the minimum supply capacity. [Published source](https://cdn.aaai.org/ojs/21234/21234-13-25247-1-2-20220628.pdf).
This guarantee applies to exactly the scaled model above; its implication is that the stated asymptotic approximation question is already settled affirmatively.
Yes. A uniformly efficiently computable online policy family exists.
The cited paper’s Theorem 1 applies to independent homogeneous Poisson arrivals, integer supply capacities, possibly overlapping groups, and the absolute-serving objective with the minimum outside expectations. Substituting \(\lambda_j=N\nu_j\) and \(b_i=Nc_i\) gives total arrival rate \(\lambda=N\), so its objective is exactly \(V_N\). Its guarantee therefore yields
\[ V_N\geq \max\left\{1-\frac1e,\, 1-\frac{1}{\sqrt{2\pi N c_{\min}}}\right\}\mathrm{OPT}_N, \qquad c_{\min}:=\min_{i\in I}c_i>0. \]
No normalization of the targets is required. [Xu and Xu, *Equity Promotion in Online Resource Allocation*, model and Theorem 1](https://cdn.aaai.org/ojs/21234/21234-13-25247-1-2-20220628.pdf).
For completeness, the following direct proof establishes a slightly weaker bound sufficient for the requested conclusion, and verifies efficiency in the stated binary input model.
Introduce a variable \(x_{ij}\) for every \((i,j)\in E\), representing allocated mass, and a variable \(s\). Solve the linear program
\[ \begin{gathered} \text{maximize }s,\\ \sum_{i:(i,j)\in E}x_{ij}\leq\nu_j \quad(j\in J),\\ \sum_{j:(i,j)\in E}x_{ij}\leq c_i \quad(i\in I),\\ \sum_{j\in g}\sum_{i:(i,j)\in E}x_{ij}\geq s\mu_g \quad(g\in\mathcal G),\\ x_{ij}\geq0,\qquad s\geq0. \end{gathered} \]
Let its optimum be \(s^*\), and choose an optimal solution \(x^*\).
This program is feasible by taking all variables zero. Moreover, summing the demand constraints gives \(\sum_{(i,j)\in E}x_{ij}\leq1\). Since \(\mathcal G\) is nonempty and each \(\mu_g>0\), the group constraints bound \(s\). Thus the feasible region is bounded and an optimum exists.
For any feasible randomized offline policy, let \(Y_{ij}\) count assignments from demand type \(j\) to supply type \(i\), and put \(x_{ij}=\mathbb E[Y_{ij}]/N\). Then:
Consequently, \((x,w)\) is LP-feasible. Taking the supremum over offline policies proves
\[ \mathrm{OPT}_N\leq s^*. \]
This argument permits overlapping groups and arbitrary targets satisfying the given hypotheses.
For each arrival of type \(j\), independently sample supply type \(i\) with probability
\[ p_{ij}:=\frac{x^*_{ij}}{\nu_j}. \]
Reject with the remaining probability \(1-\sum_i p_{ij}\). If supply \(i\) is sampled, assign the request there if a slot remains; otherwise reject.
The demand constraints and \(\nu_j>0\) ensure these are valid probabilities. The policy makes an immediate, irrevocable decision and always respects compatibility and capacity.
Fix a supply type \(i\), and define
\[ B_i:=Nc_i,\qquad a_i:=\sum_jx^*_{ij},\qquad r_i:=Na_i\leq B_i. \]
Independent marking and superposition of the input Poisson processes imply that attempts directed to \(i\) form a homogeneous Poisson process of rate \(r_i\). If \(r_i>0\), their type labels are independent, with probabilities \(Nx^*_{ij}/r_i\), and are independent of the total attempt count.
Let \(T_i\) be that count. The policy serves precisely the first \(\min(T_i,B_i)\) attempts. Therefore, writing \(Y_{ij}\) for its assignment counts,
\[ \mathbb E[Y_{ij}] =\frac{Nx^*_{ij}}{r_i}\, \mathbb E[\min(\operatorname{Pois}(r_i),B_i)]. \]
If \(r_i=0\), all \(x^*_{ij}\) incident to \(i\) vanish and all corresponding assignment counts are zero.
For a positive integer \(B\), define \(F_B(r):=\mathbb E[\min(\operatorname{Pois}(r),B)]\). Its finite expression is
\[ F_B(r) =B-e^{-r}\sum_{\ell=0}^{B-1}(B-\ell)\frac{r^\ell}{\ell!}. \]
Differentiating this expression and cancelling consecutive terms gives
\[ F'_B(r)=e^{-r}\sum_{\ell=0}^{B-1}\frac{r^\ell}{\ell!} =\Pr(\operatorname{Pois}(r)<B). \]
Since \(F_B(0)=0\), for \(r>0\),
\[ \frac{F_B(r)}r =\int_0^1\Pr(\operatorname{Pois}(rt)<B)\,dt. \]
For \(r\leq B\), couple \(\operatorname{Pois}(Bt)\) as the sum of independent variables with means \(rt\) and \((B-r)t\). This proves
\[ \frac{F_B(r)}r\geq\frac{F_B(B)}B. \]
To bound the latter quantity, let \(Z\sim\operatorname{Pois}(B)\). Because \(\mathbb E[Z-B]=0\),
\[ B-F_B(B) =\mathbb E[(B-Z)_+] =\frac12\mathbb E[|Z-B|] \leq\frac12\sqrt{\mathbb E[(Z-B)^2]} =\frac{\sqrt B}{2}. \]
The inequality is Cauchy–Schwarz; the last equality uses the Poisson variance \(B\). Hence
\[ \mathbb E[Y_{ij}] \geq Nx^*_{ij} \left(1-\frac{1}{2\sqrt{B_i}}\right). \]
Set \(B_{\min}:=Nc_{\min}\). Summing the preceding inequality over each group and using its LP constraint gives
\[ \mathbb E[M_g] \geq \left(1-\frac{1}{2\sqrt{B_{\min}}}\right)s^*\mu_g. \]
Admissibility implies \(B_{\min}\geq1\), so the factor is nonnegative. Dividing by \(\mu_g\), taking the minimum, and applying the offline upper bound proves
\[ V_N\geq \left(1-\frac{1}{2\sqrt{Nc_{\min}}}\right)s^* \geq \left(1-\frac{1}{2\sqrt{Nc_{\min}}}\right)\mathrm{OPT}_N. \]
For any fixed input and any \(\epsilon>0\), choose
\[ N_0:= \max\left\{1,\left\lceil\frac{1}{4c_{\min}\epsilon^2}\right\rceil\right\}. \]
Then every admissible \(N\geq N_0\) satisfies the requested inequality. The same policy family works for every \(\epsilon\); it does not require \(\epsilon\) as input. If \(s^*=0\), the offline upper bound gives \(\mathrm{OPT}_N=0\), so this case is also covered.
The LP has \(|E|+1\leq m\tau+1\) variables and \(m+\tau+k\) nontrivial inequalities. Its rational encoding length is polynomial in the listed input length. Standard polynomial-time rational linear programming produces an exact optimal rational solution with polynomially bounded bit length.
Each probability \(p_{ij}\) consequently has polynomial bit length. Exact sampling is also efficient: for each demand type, express its probabilities and rejection probability over a common integer denominator \(D\). The bit length of \(D\) is polynomial. Generate a uniform integer below \(D\) by drawing \(\lceil\log_2D\rceil\) independent fair bits and retrying when the resulting integer is at least \(D\). Each trial succeeds with probability greater than one half, so the expected number of trials is less than two. The case \(D=1\) is deterministic.
Finally, supply counters require \(O(L+\log N)\) bits. Thus preprocessing and expected computation per arrival are polynomial in \(m,\tau,k,L,\log N\), as required.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the assigned asymptotic approximation question affirmatively. The cited result applies to the stated model, and the direct proof independently establishes a sufficient guarantee with the required computational efficiency. No major or minor issues were found.
The published model specifies independent homogeneous Poisson arrivals, positive integer supply capacities, immediately irrevocable online decisions, possibly overlapping groups, and independently specified targets in \((0,1)\). Its absolute-serving objective places the minimum outside expectations, and its benchmark permits observing the entire arrival sequence. Theorem 1 gives the competitive bound stated by the prover. These features are confirmed in the [published model and Theorem 1](https://cdn.aaai.org/ojs/21234/21234-13-25247-1-2-20220628.pdf).
The substitution \(\lambda_j=N\nu_j\), \(b_i=Nc_i\) satisfies those hypotheses for every admissible \(N\). Moreover,
\[ \sum_j\lambda_j=N,\qquad \frac{\mathbb E[X_g]}{N\mu_g} =\frac{\mathbb E[M_g]}{\mu_g}. \]
Thus the objectives and offline benchmarks match. The minimum integer supply capacity becomes \(Nc_{\min}\), giving the claimed bound. No condition requiring the targets to sum to one appears in the general model or theorem.
The direct proof below also supplies the bit-complexity justification required by the task.
Every LP constraint has the correct interpretation:
The existence argument is valid. The zero solution is feasible. Summing the demand constraints bounds total allocated mass by \(1\), hence bounds every nonnegative allocation variable. Any group constraint then bounds \(s\) by \(1/\mu_g\). The feasible region is closed and bounded, so the linear objective attains its maximum.
For an arbitrary feasible offline policy, the variables \(x_{ij}=\mathbb E[Y_{ij}]/N\) satisfy the demand and supply constraints. Assignment counts have finite expectations because they are bounded by arrival counts and capacities. If its objective value is \(w\), the definition of the minimum gives every group constraint with \(s=w\).
Consequently every offline policy has value at most \(s^*\). Taking a supremum does not require an optimal offline policy to exist, so \(\mathrm{OPT}_N\leq s^*\) follows rigorously.
Overlapping groups cause no problem: each constraint is evaluated separately.
The probabilities \(p_{ij}=x^*_{ij}/\nu_j\) are defined because every listed demand mass is positive. The demand constraints imply their sum is at most one. Independent sampling, rejection, and capacity checking therefore define a feasible online policy.
For a fixed supply \(i\), independent marking and superposition apply to the independent input Poisson processes. The attempted assignments have rate
\[ r_i=N\sum_jx^*_{ij}\leq Nc_i=B_i. \]
When \(r_i>0\), their labels have the stated probabilities and are independent of the total attempt count. Because acceptance depends only on the attempt’s position relative to capacity, serving the first \(\min(T_i,B_i)\) attempts yields exactly the displayed expectation formula.
The case \(r_i=0\) is handled correctly: nonnegativity forces every incident \(x^*_{ij}\) to vanish.
The finite expression for \(F_B(r)\) correctly accounts for the shortfall below capacity. Differentiation gives
\[ F'_B(r)=\Pr(\operatorname{Pois}(r)<B). \]
Integrating from zero and substituting the integration variable produces the stated expression for \(F_B(r)/r\).
For \(0<r\leq B\), the proposed coupling makes the Poisson variable with mean \(Bt\) at least the one with mean \(rt\). The event of being below \(B\) therefore has no larger probability for the former. The resulting inequality has the correct direction.
At mean \(B\), the shortfall identity is valid. A centered integrable random variable has equal expected positive and negative parts, giving
\[ B-F_B(B) =\frac12\mathbb E[|Z-B|] \leq\frac12\sqrt{\mathbb E[(Z-B)^2]} =\frac{\sqrt B}{2}. \]
Cauchy–Schwarz and the Poisson variance justify the inequality and final equality. Substitution into the assignment expectation gives the claimed edgewise bound, including zero allocation variables.
Since \(B_i\geq B_{\min}\), each edgewise service factor is at least \(1-1/(2\sqrt{B_{\min}})\). Summing within a group and applying its LP constraint proves the groupwise inequality.
Admissibility ensures \(B_{\min}\geq1\), so the factor is nonnegative. Multiplication of the offline upper bound therefore preserves the inequality direction.
The displayed choice of \(N_0\) ensures \(1/(2\sqrt{Nc_{\min}})\leq\epsilon\) for every admissible \(N\geq N_0\). The policy does not depend on \(\epsilon\), satisfying the requested quantifier order. Values \(\epsilon\geq1\) also cause no difficulty.
The zero-optimum case is explicitly covered. Empty compatibility graphs and unserviceable groups are therefore included.
The LP size and rational coefficient lengths are polynomial in the explicit input encoding. The standard polynomial-time theorem for rational linear programming applies: this LP is feasible with a finite attained optimum, and an exact optimal rational solution of polynomial encoding length can be computed.
Dividing by positive rational demand masses preserves polynomial bit length. A common denominator can be formed with polynomial bit length because each demand type has only polynomially many probabilities.
The rejection sampler is exact. For \(D>1\), drawing \(\lceil\log_2D\rceil\) bits succeeds with probability strictly greater than one half; \(D=1\) is correctly treated separately. Selecting the corresponding category from cumulative integer weights also takes polynomial time.
Capacity counters have the stated \(O(L+\log N)\) bit bound. Thus both preprocessing and expected computation per arrival meet the task’s uniform efficiency requirement.
Required clarification: none.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.