Answer: —
Proposition 2 — class: other
Given \(n\) items, a distribution \(\mu\) over observable worker types \(t\), type-specific Gaussian response variances \(\sigma_t^2\), per-capita task capacities \(b_t\), a Gaussian prior with variance \(\sigma_x^2\), and a total task budget \(B\), choose query masses \(q_{ijt}\ge 0\) with \(\sum_{i<j}q_{ijt}\le b_t\mu_t\) and \(\sum_{t,i<j}q_{ijt}=B\) to maximize \(\frac12\log\det\!\left(I+\sigma_x^2\sum_{t,i<j}\frac{q_{ijt}}{\sigma_t^2}d_{ij}d_{ij}^{\top}\right)\), where \(d_{ij}=e_i-e_j\). Does this continuous design problem admit an efficient \(\varepsilon\)-optimal algorithm, and how does its optimum compare with the paper’s sequential greedy EIG rule?
There are \(m=n\ge2\) items. A society is given by its support: \(\tau\) observable worker types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type has binary-rational variance \(\sigma_t^2>0\) and per-capita capacity \(b_t\ge0\). The prior is \(x\sim\mathcal N(0,\sigma_x^2 I_m)\), with binary-rational \(\sigma_x^2>0\); a query of type \(t\) on \(i<j\) observes \(x_i-x_j\) plus independent Gaussian noise of variance \(\sigma_t^2\). Every pair is available, and repeated queries are allowed.
The binary-rational budget satisfies \(0<B\le\sum_t b_t\mu_t\). Choose real masses \(q_{ijt}\ge0\) satisfying \(\sum_{i<j}q_{ijt}\le b_t\mu_t\) and \(\sum_{t,i<j}q_{ijt}=B\).
With \(d_{ij}=e_i-e_j\), maximize \(F(q)=\frac12\log\det\bigl(I_m+\sigma_x^2\sum_{t,i<j}(q_{ijt}/\sigma_t^2)d_{ij}d_{ij}^{\top}\bigr)\); logarithms are natural. Write \(F^*=\max_q F(q)\). Additive \(\varepsilon\)-optimality means \(F(q)\ge F^*-\varepsilon\), where \(0<\varepsilon<1\) is binary rational; \(L\) is the total input bit length.
For comparison, on homogeneous instances \(\tau=1\) with integer \(B\), sequential greedy EIG starts with no observations and makes \(B\) unit queries, each maximizing the posterior-predictive expectation of KL divergence from the current posterior to the updated posterior. Ties use lexicographic order; let \(q^{\mathrm{gr}}\) be its query counts.
Does this continuous problem admit an additive \(\varepsilon\)-optimal algorithm polynomial in \(m,\tau,L,\log(1/\varepsilon)\), or is achieving this accuracy NP-hard?
On the homogeneous integer-budget instances, what is the sharp worst-case gap \(F^*-\mathbb E[F(q^{\mathrm{gr}})]\) as a function of \(m,B,\sigma_x^2/\sigma_1^2\)?
For discrete Gaussian queries, [Xu et al.](https://ojs.aaai.org/index.php/AAAI/article/view/11619/11478) give rank-one posterior updates and constant-time pairwise EIG evaluation given stored posterior parameters; this is a local computation result, not a global optimality guarantee.
For continuous designs, [Alexanderian](https://arxiv.org/html/2212.11466v3) establishes the Gaussian EIG–posterior-log-determinant identity, and [Boyd–Vandenberghe](https://www.seas.ucla.edu/~vandenbe/cvxbook/bv_cvxbook.pdf) treat ordinary fractional D-optimal design as convex optimization; these results do not state the capacity-constrained problem and greedy-gap comparison above.
The continuous problem has an exact rational optimum computable in polynomial time.
For the greedy comparison, I prove exact gaps:
The all-budget formulas for $m=5,6$ and the formula at $B=m+1$ extend the results in the notes. The sharp gap for $m\ge7$ and $B>m+1$ remains unresolved here.
Write
$$
r=m-1,\qquad M=\binom m2,\qquad a_t=b_t\mu_t.
$$
Order the supported types so that
$$
\sigma_1^2\le\cdots\le\sigma_\tau^2.
$$
Define
$$
Q_t^*=
\min\left\{
a_t,\,
\max\left\{0,B-\sum_{u<t}a_u\right\}
\right\},
\qquad
S^*=\sum_{t=1}^{\tau}\frac{Q_t^*}{\sigma_t^2}.
$$
Then
$$
q_{ijt}^*=\frac{Q_t^*}{M}
$$
is an exact optimum, with value
$$
F^*=\frac r2\log\left(1+\frac{2\sigma_x^2S^*}{r}\right).
$$
Proof. For any feasible design, let
$$
Q_t=\sum_{i<j}q_{ijt},
\qquad
S=\sum_t\frac{Q_t}{\sigma_t^2},
\qquad
L_q=\sum_{t,i<j}\frac{q_{ijt}}{\sigma_t^2}d_{ij}d_{ij}^{\top}.
$$
The matrix $L_q$ is positive semidefinite, annihilates $\mathbf1$, and has trace $2S$. Consequently, its $r$ eigenvalues on $\mathbf1^\perp$, including zeros, have sum $2S$. Concavity of the logarithm gives
$$
F(q)\le
\frac r2\log\left(1+\frac{2\sigma_x^2S}{r}\right).
$$
Put
$$
P=I_m-\frac{\mathbf1\mathbf1^\top}{m}.
$$
Directly comparing diagonal and off-diagonal entries gives
$$
\sum_{i<j}d_{ij}d_{ij}^{\top}=mP.
$$
Therefore uniform allocation within each type gives
$$
L_q=\frac{mS}{M}P=\frac{2S}{r}P,
$$
and attains the preceding bound.
It remains to maximize $S$ over
$$
0\le Q_t\le a_t,\qquad \sum_tQ_t=B.
$$
If a type of smaller variance has unused capacity while a type of larger variance receives positive mass, transferring mass to the former does not decrease $S$. Successively making these transfers produces the displayed $Q_t^*$. The assumption $B\le\sum_ta_t$ ensures that their sum is $B$.
All operations producing $q^*$ are rational comparisons and arithmetic. Products and sums of input rationals have polynomial bit length, and the output has $M\tau$ entries. Thus the algorithm runs in time polynomial in $m,\tau,L$. It is additive $\varepsilon$-optimal for every allowed $\varepsilon$, without evaluating any logarithm. $\square$
For homogeneous instances, set
$$
\alpha=\frac{\sigma_x^2}{\sigma_1^2}.
$$
Let $L_k$ be the multigraph Laplacian after $k$ unit queries. Gaussian conditioning gives posterior covariance
$$
C_k=\sigma_x^2(I_m+\alpha L_k)^{-1}.
$$
In particular, this covariance depends on the query counts and not on the observed values.
Here is the precise KL identity needed below. For positive definite covariance matrices $V_1,V_2$,
$$
D_{\mathrm{KL}}\!\left(
\mathcal N(h_1,V_1)\,\middle\|\,\mathcal N(h_2,V_2)
\right)
=
\frac12\left[
\log\frac{\det V_2}{\det V_1}
-m+\operatorname{tr}(V_2^{-1}V_1)
+(h_2-h_1)^\top V_2^{-1}(h_2-h_1)
\right].
$$
This identity is also stated in [Alexanderian’s Gaussian D-optimality derivation](https://arxiv.org/html/2212.11466v3).
Suppose the current posterior is $\mathcal N(h,C)$ and the next query uses $d=d_{ij}$. Write $v=\sigma_1^2$ and
$$
s=\frac{d^\top Cd}{v}.
$$
The updated covariance and mean are
$$
C'=C-\frac{Cdd^\top C}{v+d^\top Cd},
\qquad
h'=h+\frac{Cd}{v+d^\top Cd}(y-d^\top h).
$$
Under the posterior-predictive distribution,
$$
\mathbb E[h'-h]=0,\qquad
\mathbb E[(h'-h)(h'-h)^\top]=C-C'.
$$
Also,
$$
C'^{-1}=C^{-1}+\frac{dd^\top}{v},
\qquad
\frac{\det C}{\det C'}=1+s.
$$
Substituting into the KL identity yields
$$
\mathbb E[D_{\mathrm{KL}}(\text{updated}\,\|\,\text{current})]
=\frac12\log(1+s).
$$
Indeed, the expected trace and mean terms sum to $m$.
In the literal direction requested in the question,
$$
\mathbb E[D_{\mathrm{KL}}(\text{current}\,\|\,\text{updated})]
=s-\frac12\log(1+s),
$$
because
$$
\operatorname{tr}(C'^{-1}C)=m+s,
\qquad
\operatorname{tr}(C'^{-1}(C-C'))=s.
$$
Both functions are strictly increasing in $s\ge0$. Thus either convention selects precisely the pairs maximizing
$$
R_k(i,j)=d_{ij}^\top(I_m+\alpha L_k)^{-1}d_{ij}.
$$
Lexicographic tie-breaking consequently makes the entire greedy query sequence deterministic. Hence
$$
\mathbb E[F(q^{\mathrm{gr}})]=F(q^{\mathrm{gr}}).
$$
The continuous benchmark is
$$
F^*=\frac r2\log\left(1+\frac{2\alpha B}{r}\right).
$$
At fixed $m,B,\alpha$, every feasible homogeneous instance has this same greedy sequence and benchmark: its capacity affects only feasibility. Therefore each exact gap below is also the sharp worst-case gap for its stated parameters.
There is a unique $\rho\in(0,1)$ satisfying
$$
\alpha=\frac{\rho}{(1-\rho)^2},
$$
because the right-hand side increases continuously from zero to infinity.
For a path on $s$ vertices, define
$$
D_s=\det(I_s+\alpha L_{P_s})
=
\frac{1-\rho^{2s}}
{(1-\rho^2)(1-\rho)^{2s-2}}.
$$
In particular, $D_1=1$.
Starting with $m$ component sizes equal to $1$, repeatedly replace the two smallest sizes by their sum. Let $\mathcal S_B$ be the resulting multiset after $B$ replacements. For $B\le m-1$,
$$
\boxed{
F^*-F(q^{\mathrm{gr}})
=
\frac r2\log\left(1+\frac{2\alpha B}{r}\right)
-\frac12\sum_{s\in\mathcal S_B}\log D_s.
}
$$
The following calculation proves the asserted greedy structure.
Let
$$
K_s=(I_s+\alpha L_{P_s})^{-1}.
$$
For consecutively indexed path vertices,
$$
(K_s)_{ij}
=
\frac{1-\rho}{1+\rho}
\frac{
\rho^{|i-j|}
+\rho^{i+j-1}
+\rho^{2s+1-i-j}
+\rho^{2s-|i-j|}
}
{1-\rho^{2s}}.
$$
For verification when $s\ge2$, put
$$
f_i=\rho^{-i}+\rho^{i-1},
\qquad
g_i=\rho^i+\rho^{2s+1-i},
\qquad
\kappa=\frac{1-\rho}{(1+\rho)(1-\rho^{2s})}.
$$
For $i\le j$, the proposed entry is $\kappa f_i g_j$. The relation
$$
1+2\alpha=\alpha(\rho+\rho^{-1})
$$
verifies the interior recurrence. The endpoint conditions follow from $f_0=f_1$ and $g_{s+1}=g_s$. The diagonal equation follows from
$$
\alpha(f_{j+1}g_j-f_jg_{j+1})
=
\frac{1+\rho}{1-\rho}(1-\rho^{2s})
=\kappa^{-1}.
$$
The case $s=1$ is direct.
The maximum diagonal entry occurs at an endpoint and equals
$$
v_s=
\frac{(1-\rho)(1+\rho^{2s-1})}{1-\rho^{2s}}
=
1-\rho+
\frac{(1-\rho^2)\rho^{2s-1}}{1-\rho^{2s}}.
$$
To see endpoint maximality, the position-dependent diagonal terms are
$$
\rho^{2i-1}+\rho^{2s+1-2i}.
$$
Their exponents have fixed sum; convexity of the exponential makes their sum largest at an endpoint. The last expression for $v_s$ also shows that $v_s>1-\rho$ and that $v_s$ strictly decreases with $s$.
The covariance between path endpoints is
$$
c_s=\frac{(1-\rho^2)\rho^{s-1}}{1-\rho^{2s}}.
$$
Their pair score is therefore
$$
R_{\mathrm{end}}(s)
=
2(v_s-c_s)
=
2(1-\rho)\frac{1-\rho^{s-1}}{1+\rho^s}
<2(1-\rho).
$$
Every within-path pair has score below $2(1-\rho)$. Indeed, remove the edges attaching its intervening subpath to the rest of the path. This decreases the positive definite precision matrix, so it increases the inverse in positive semidefinite order. The original score is at most the endpoint score of that isolated subpath.
Conversely, endpoints in different components of sizes $s,t$ have score
$$
v_s+v_t>2(1-\rho).
$$
Thus greedy joins different components whenever more than one remains. It chooses endpoints, preserving the path structure, and chooses the two smallest components because $v_s$ decreases with $s$. This proves the path-merging rule.
For completeness, the determinant calculation uses leading tridiagonal determinants $h_k$ satisfying
$$
h_0=1,\qquad h_1=1+\alpha,\qquad
h_k=(1+2\alpha)h_{k-1}-\alpha^2h_{k-2}.
$$
Solving this recurrence gives
$$
h_k=
\frac{1+\rho^{2k+1}}{(1+\rho)(1-\rho)^{2k}}.
$$
For $s\ge2$,
$$
D_s=(1+\alpha)h_{s-1}-\alpha^2h_{s-2},
$$
which gives the displayed expression for $D_s$. Determinants multiply across path components, completing the gap proof.
Assume $m\ge3$. After $m-1$ queries, greedy has one path on all vertices. The function $R_{\mathrm{end}}(s)$ strictly increases with $s$: writing $t=\rho^s$, its variable factor is
$$
\frac{1-t/\rho}{1+t},
$$
which strictly decreases with $t$.
Every pair other than the full path’s endpoints spans a shorter subpath. The preceding edge-removal bound therefore proves that the full path’s endpoints uniquely maximize the next score. Greedy closes the path into $C_m$.
Its determinant is
$$
D_{C_m}
=
\prod_{j=0}^{m-1}
\frac{1-2\rho\cos(2\pi j/m)+\rho^2}{(1-\rho)^2}
=
\frac{(1-\rho^m)^2}{(1-\rho)^{2m}}.
$$
The last equality follows by factoring the numerator over the $m$th roots of unity. Hence
$$
\boxed{
F^*-F(q^{\mathrm{gr}})
=
\frac r2\log\left(1+\frac{2\alpha m}{r}\right)
-\log\left(\frac{1-\rho^m}{(1-\rho)^m}\right).
}
$$
For vertices at cyclic distance $h$, the cycle inverse has entry
$$
(K_{C_m})_{uv}
=
\frac{1-\rho}{1+\rho}
\frac{\rho^h+\rho^{m-h}}{1-\rho^m}.
$$
One verification is to periodize the infinite-line inverse kernel
$$
\frac{1-\rho}{1+\rho}\rho^{|u-v|}.
$$
That kernel satisfies the tridiagonal equations because
$$
1+2\alpha=\alpha(\rho+\rho^{-1}),
\qquad
\frac{1-\rho}{1+\rho}\bigl(1+2\alpha(1-\rho)\bigr)=1.
$$
Summing its shifts by multiples of $m$ gives the displayed cycle entry.
Thus the score at distance $h$ is
$$
R_{C_m}(h)
=
\frac{2(1-\rho)}{1+\rho}
\frac{(1-\rho^h)(1-\rho^{m-h})}{1-\rho^m}.
$$
For integer $h<\lfloor m/2\rfloor$,
$$
\bigl(\rho^{h+1}+\rho^{m-h-1}\bigr)
-\bigl(\rho^h+\rho^{m-h}\bigr)
=
(1-\rho)(\rho^{m-h-1}-\rho^h)<0.
$$
Therefore the score strictly increases up to maximum cyclic distance. All pairs at that distance have the same score.
Put
$$
h_*=\left\lfloor\frac m2\right\rfloor.
$$
By the matrix determinant lemma, the next query multiplies the determinant by $1+\alpha R_{C_m}(h_*)$. Consequently, for every $m\ge3$,
$$
\boxed{
F^*-F(q^{\mathrm{gr}})
=
\frac r2\log\left(1+\frac{2\alpha(m+1)}r\right)
-\frac12\log D_{C_m}
-\frac12\log\bigl(1+\alpha R_{C_m}(h_*)\bigr)
\quad\text{when }B=m+1.
}
$$
For $m=3$, this query repeats an existing pair, as permitted.
When $B\le\lfloor m/2\rfloor$, greedy produces a matching, so
$$
F^*-F(q^{\mathrm{gr}})
=
\frac r2\log\left(1+\frac{2\alpha B}{r}\right)
-\frac B2\log(1+2\alpha).
$$
More generally, the path determinant formula gives
$$
\frac{D_s}{\alpha^{s-1}}
=
\frac{1-\rho^{2s}}{1-\rho^2}\rho^{-(s-1)}
\longrightarrow s
\qquad\text{as }\alpha\longrightarrow\infty.
$$
Since $\mathcal S_B$ has $m-B$ components,
$$
F^*-F(q^{\mathrm{gr}})
=
\frac{r-B}{2}\log\alpha
+\frac r2\log\left(\frac{2B}{r}\right)
-\frac12\sum_{s\in\mathcal S_B}\log s
+o(1).
$$
Thus the gap is unbounded in $\alpha$ whenever $B<m-1$. Taking $\alpha$ through powers of two respects the rational-input requirement.
For $m=2$, there is only one pair, so the gap is always zero.
For $m=3$, let the three edge counts be $a,b,c$, with sum $B$. Expansion by principal minors gives
$$
\det(I_3+\alpha L)
=
1+2\alpha B+3\alpha^2(ab+ac+bc).
$$
Increasing the count $a$ increases the quadratic term by $b+c=B-a$. Greedy therefore increments a smallest count. The final counts differ by at most one, and
$$
ab+ac+bc=\left\lfloor\frac{B^2}{3}\right\rfloor.
$$
With $\delta_B=0$ if $3$ divides $B$, and $\delta_B=1$ otherwise, the exact gap is
$$
\boxed{
F^*-F(q^{\mathrm{gr}})
=
-\frac12\log\left(
1-\frac{\delta_B\alpha^2}{(1+\alpha B)^2}
\right).
}
$$
Suppose greedy completes one copy of $K_m$ after $M$ queries, with the same prefix structure for every positive parameter.
After $k$ such layers,
$$
L_{Mk}=kmP.
$$
Set
$$
c_k=1+m\alpha k,\qquad \beta=\frac{\alpha}{c_k}.
$$
For a prefix Laplacian $L_s$ of the next layer,
$$
\det(I_m+\alpha(kmP+L_s))
=
c_k^r\det(I_m+\beta L_s).
$$
Moreover, for every difference vector $d$,
$$
d^\top(I_m+\alpha(kmP+L_s))^{-1}d
=
c_k^{-1}d^\top(I_m+\beta L_s)^{-1}d.
$$
Thus score ordering, including ties, is the ordering for parameter $\beta$.
If
$$
D_s^{(m)}(z)=\det(I_m+zL_s),
\qquad B=Mk+s,\quad 0\le s<M,
$$
the common scalar factor cancels from the gap:
$$
\boxed{
F^*-F(q^{\mathrm{gr}})
=
\frac r2\log\left(1+\frac{2\beta s}{r}\right)
-\frac12\log D_s^{(m)}(\beta).
}
$$
It remains to verify complete layers.
Through four queries, the path argument gives an edge, a matching, a path, and a cycle. For the cycle, opposite and adjacent pair scores are respectively
$$
\frac{2}{1+2z},
\qquad
\frac1{1+2z}+\frac1{1+4z}.
$$
The opposite pair is strictly preferred.
After it is added, let $d$ denote the sole missing pair and put $c=1+4z$. On $\mathbf1^\perp$, precision is $cI-zdd^\top$. The missing pair’s score is
$$
\frac2{c-2z}.
$$
A present pair with difference vector $f$ has score
$$
\frac2c+\frac{z(f^\top d)^2}{c(c-2z)}.
$$
Here $(f^\top d)^2$ is either zero or one, so its score is strictly smaller. Query six completes $K_4$.
The prefix determinants are:
| $s$ | $D_s^{(4)}(z)$ |
|---|---|
| $0$ | $1$ |
| $1$ | $1+2z$ |
| $2$ | $(1+2z)^2$ |
| $3$ | $(1+2z)(1+4z+2z^2)$ |
| $4$ | $(1+2z)^2(1+4z)$ |
| $5$ | $(1+2z)(1+4z)^2$ |
Their computation follows either from the path determinant or from the precision matrices just displayed. The complete-layer reduction supplies the all-budget gap.
For $m=5$, the lexicographic greedy sequence in each layer is
$$
12,\ 34,\ 15,\ 23,\ 45,\ 13,\ 24,\ 25,\ 14,\ 35.
$$
For $m=6$, it is
$$
12,\ 34,\ 56,\ 13,\ 25,\ 46,\ 16,\ 24,\ 35,\ 14,\ 23,\ 15,\ 26,\ 36,\ 45.
$$
Here $ij$ denotes the pair $\{i,j\}$. Each sequence contains every pair exactly once.
These statements hold for every positive parameter. Below I give exact polynomial certificates for all comparisons after the cycle; the path-merging proof establishes the preceding queries.
Define
$$
A_j(z)=1+jz,\qquad H(z)=1+5z+5z^2.
$$
The prefix determinants are:
| $s$ | $D_s^{(5)}(z)$ | $D_s^{(6)}(z)$ |
|---|---|---|
| $0$ | $1$ | $1$ |
| $1$ | $A_2$ | $A_2$ |
| $2$ | $A_2^2$ | $A_2^2$ |
| $3$ | $A_1A_2A_3$ | $A_2^3$ |
| $4$ | $(1+3z+z^2)H$ | $A_2^2(1+4z+2z^2)$ |
| $5$ | $H^2$ | $A_1A_2A_3(1+4z+z^2)$ |
| $6$ | $H(1+7z+11z^2)$ | $A_1^2A_3^2A_4$ |
| $7$ | $A_2A_3A_4A_5$ | $A_1A_2A_3^2A_5$ |
| $8$ | $A_3^2A_5^2$ | $A_3^3(1+7z+8z^2)$ |
| $9$ | $A_3A_5^3$ | $A_3^4A_6$ |
| $10$ | $A_5^4$ | $A_3^3A_5A_6$ |
| $11$ | — | $A_3^2A_5^2A_6$ |
| $12$ | — | $A_3A_4A_5A_6^2$ |
| $13$ | — | $A_4^2A_6^3$ |
| $14$ | — | $A_4A_6^4$ |
| $15$ | — | $A_6^5$ |
Arguments of the $A_j$ and $H$ factors are $z$ throughout the table.
Exact comparison certificate. Let $L_s$ be the Laplacian of the first $s$ listed pairs, and for any candidate pair $e$ define
$$
P_{s,e}(z)=\det(I_m+z(L_s+d_ed_e^\top)).
$$
The determinant lemma gives
$$
P_{s,e}(z)
=
D_s^{(m)}(z)
\left(1+z\,d_e^\top(I_m+zL_s)^{-1}d_e\right).
$$
Thus greedy maximizes $P_{s,e}(z)$.
Let $e_s$ be the next listed pair. In the following table, $T_s$ is the set of candidates for which
$$
P_{s,e_s}(z)-P_{s,e}(z)
$$
is identically zero. For every other candidate, write
$$
P_{s,e_s}(z)-P_{s,e}(z)
=
\sum_{j=2}^{m-1}h_{s,e,j}z^j.
$$
The last column gives the coordinatewise minima of these coefficient vectors over $e\notin T_s$.
| $m$ | $s$ | $T_s$ | $\bigl(\min h_{s,e,2},\ldots,\min h_{s,e,m-1}\bigr)$ |
|---|---|---|---|
| $5$ | $5$ | $\{13,14,24,25,35\}$ | $(2,10,10)$ |
| $5$ | $6$ | $\{24,25\}$ | $(1,8,15)$ |
| $5$ | $7$ | $\{25,35\}$ | $(1,10,25)$ |
| $5$ | $8$ | $\{14,35\}$ | $(2,16,30)$ |
| $5$ | $9$ | $\{35\}$ | $(3,30,75)$ |
| $6$ | $6$ | $\{16,24,35\}$ | $(0,2,8,6)$ |
| $6$ | $7$ | $\{24,35\}$ | $(0,2,8,6)$ |
| $6$ | $8$ | $\{35\}$ | $(1,14,57,72)$ |
| $6$ | $9$ | $\{14,15,23,26,36,45\}$ | $(2,18,54,54)$ |
| $6$ | $10$ | $\{23,26,36\}$ | $(1,12,45,54)$ |
| $6$ | $11$ | $\{15,26,36,45\}$ | $(1,12,47,60)$ |
| $6$ | $12$ | $\{26,36\}$ | $(1,18,108,216)$ |
| $6$ | $13$ | $\{36,45\}$ | $(2,32,168,288)$ |
| $6$ | $14$ | $\{45\}$ | $(3,54,324,648)$ |
Here are explicit coefficient identities specifying and verifying the finite calculations in both tables. For any candidate Laplacian $G$,
$$
\det(I_m+zG)=\sum_{j=0}^{m-1}E_j(G)z^j,
$$
where
$$
E_j(G)=\sum_{\substack{U\subseteq\{1,\ldots,m\}\\|U|=j}}\det G[U,U].
$$
Equivalently, starting with $E_0=1$, they can be computed from
$$
jE_j
=
\sum_{\ell=1}^{j}
(-1)^{\ell-1}E_{j-\ell}\operatorname{tr}(G^\ell).
$$
This recurrence follows by differentiating $\det(I_m+zG)$ and expanding
$$
\operatorname{tr}\bigl(G(I_m+zG)^{-1}\bigr)
=
\sum_{\ell\ge1}(-1)^{\ell-1}\operatorname{tr}(G^\ell)z^{\ell-1}.
$$
The Laplacian entries used in these calculations are
$$
(L_s)_{ij}
=
-\#\{\text{occurrences of }ij\text{ among the first }s\text{ pairs}\}
\quad(i\ne j),
$$
with diagonal entries equal to the incident counts. These identities give all table entries by integer arithmetic.
For example, at $m=6,s=6$, the selected pair is $16$. The complete list of difference polynomials, grouped by equal value, is
$$
P_{6,16}-P_{6,e}
=
\begin{cases}
2z^2(1+z)(1+3z)(1+4z),
&e\in\{12,13,25,34,46,56\},\\
2z^3(1+z)(1+3z),
&e\in\{14,15,23,26,36,45\},\\
0,
&e\in\{16,24,35\}.
\end{cases}
$$
The nonzero coefficient vectors are
$$
(2,16,38,24),\qquad (0,2,8,6),
$$
giving the stated coordinatewise minimum.
Every minimum vector in the certificate is nonnegative and has a positive coordinate. Hence every candidate outside $T_s$ has strictly smaller determinant for every $z>0$. The lexicographically smallest member of $T_s$ is exactly the next listed pair. This proves all remaining greedy choices.
Both layers therefore complete $K_m$. Applying the complete-layer reduction proves the following all-budget formulas:
$$ \boxed{ F^*-F(q^{\mathrm{gr}}) = 2\log\left(1+\frac{\beta s}{2}\right) -\frac12\log D_s^{(5)}(\beta). } $$
$$ \boxed{ F^*-F(q^{\mathrm{gr}}) = \frac52\log\left(1+\frac{2\beta s}{5}\right) -\frac12\log D_s^{(6)}(\beta). } $$
In particular, the gap is zero at every complete-layer budget in these cases.
The following bounds apply to every $m,B,\alpha$, but are not asserted to be sharp.
Let
$$
\Delta=F^*-F(q^{\mathrm{gr}}),
\qquad a=\frac r{2\alpha}.
$$
Then
$$
0\le\Delta
\le
\frac12\sum_{j=1}^{r-1}
\log\left(
\frac{(a+B)(a+j)}{a(a+B+j)}
\right).
$$
Proof. Let $\lambda_1,\ldots,\lambda_r$ be the eigenvalues of $I_m+\alpha L_k$ on $\mathbf1^\perp$. Their sum is $r+2\alpha k$. Averaging scaled pair scores gives
$$
\frac1M\sum_{i<j}\alpha R_k(i,j)
=
\frac{2\alpha}{r}\sum_{\ell=1}^{r}\lambda_\ell^{-1}.
$$
Cauchy–Schwarz yields
$$
\sum_{\ell=1}^{r}\lambda_\ell^{-1}
\ge\frac{r^2}{r+2\alpha k}.
$$
The selected query therefore has scaled score at least $r/(a+k)$, and increases $F$ by at least
$$
\frac12\log\left(1+\frac r{a+k}\right).
$$
Summing and cancelling common factors gives
$$
F(q^{\mathrm{gr}})
\ge
\frac12\sum_{j=0}^{r-1}
\log\left(\frac{a+B+j}{a+j}\right).
$$
Subtracting this from $F^*=\frac r2\log((a+B)/a)$ proves the bound. $\square$
There is also a lower bound applying to every integral design. Write
$$
B=Mk+s,\qquad 0\le s<M.
$$
Then
$$
\Delta\ge
\frac{\alpha^2s(M-s)}
{2M(1+2\alpha B)^2}.
$$
Proof. Put
$$
H=1+2\alpha B,\qquad c=1+\frac{2\alpha B}{r}.
$$
Every contrast precision eigenvalue lies in $[1,H]$, and their average is $c$. Since $(\log x)''\le-H^{-2}$ on this interval,
$$
\log\lambda
\le
\log c+\frac{\lambda-c}{c}
-\frac{(\lambda-c)^2}{2H^2}.
$$
Summing cancels the linear terms. Therefore, for any integral design $q$,
$$
F^*-F(q)
\ge
\frac{\alpha^2}{4H^2}
\left\|L_q-\frac{2B}{r}P\right\|_{\mathrm F}^2
\ge
\frac{\alpha^2}{2H^2}
\sum_{i<j}\left(q_{ij}-\frac BM\right)^2.
$$
The last inequality uses the two symmetric off-diagonal entries for each pair.
For integer counts summing to $B$, transferring one unit between counts differing by at least two strictly decreases the final squared sum. Its minimum is attained by $s$ counts equal to $k+1$ and $M-s$ counts equal to $k$, giving minimum $s(M-s)/M$. This proves the assertion. $\square$
The continuous complexity question is settled exactly. The formulas above determine the sharp greedy gap for every $m$ through $B=m+1$, and for all budgets when $m\le6$.
The missing result is an exact characterization for $m\ge7$ and $B>m+1$. The general bounds do not determine that value, and the complete-layer argument proved for five and six vertices has not been established for arbitrary $m$.
⟨structured verdict parsed — rendered above⟩
Overall assessment: partial, with a correct resolution of the continuous complexity question. The continuous optimizer is valid, and the stated greedy-gap formulas and bounds check out. The output explicitly leaves the sharp gap unresolved for $m\ge7$ and $B>m+1$, so it does not fully answer USER_TASK.
The finite certificates for $m=5,6$ were independently recomputed using exact integer arithmetic. Every prefix determinant, listed tie set, and coordinatewise coefficient minimum agrees with the output. There is no computational error in those tables.
1. Continuous optimum — verified.
For a feasible design, $L_q$ is positive semidefinite, annihilates $\mathbf1$, and has trace $2S$. Thus its $r=m-1$ eigenvalues on $\mathbf1^\perp$ are nonnegative and sum to $2S$. Applying concavity of $\log(1+\sigma_x^2\lambda)$ gives the stated upper bound. Positive definiteness of $I_m+\sigma_x^2L_q$ ensures that all logarithms are defined.
The identity
$$
\sum_{i<j}d_{ij}d_{ij}^{\top}=mP
$$
is correct. Consequently, uniform allocation within each type produces precisely the contrast eigenvalues required to attain the bound.
The remaining optimization over type totals is a linear allocation problem with coefficients $1/\sigma_t^2$ in nonincreasing order. The transfer argument correctly establishes optimality of the displayed $Q_t^*$. Equal variances cause no difficulty: transfers between such types preserve the objective. Zero capacities are also handled by the formula. The budget assumption ensures feasibility and $\sum_tQ_t^*=B$.
The bit-complexity claim is sound under the intended rational encoding of capacities. Sorting, rational arithmetic, and producing $M\tau$ rational entries require polynomial time and polynomial output bit length. No evaluation of logarithms is needed to return an optimal design. This establishes the requested additive approximation guarantee, including its dependence on $\log(1/\varepsilon)$.
Minor encoding clarification. The task explicitly describes several inputs as binary rational but does not separately specify the encoding of $b_t$. The proof assumes rational capacities when asserting rational arithmetic and an exact rational optimizer. The minimum clarification is to state explicitly that the capacities have binary-rational encodings, as the finite-input formulation evidently intends.
2. Gaussian updates and the literal KL direction — verified.
The covariance and mean update formulas have positive denominators because $v>0$ and $C$ is positive definite. The posterior-predictive covariance of the mean increment is correctly given by $C-C'$.
The Gaussian KL identity is stated correctly, with the inverse covariance belonging to the distribution in the second argument. It also matches the identity in [Alexanderian’s preliminaries](https://arxiv.org/html/2212.11466v3).
Both substitutions check out:
Both expressions are strictly increasing on $s\ge0$. Therefore the literal KL direction in the task produces the same maximizing pair as the usual EIG direction.
The covariance depends only on previous query counts. Together with lexicographic tie-breaking, this proves that the greedy sequence and its final objective are deterministic. Removing the expectation is justified.
At fixed $m,B,\alpha$, homogeneous capacity affects feasibility but neither the benchmark nor the greedy sequence. Accordingly, the exact gaps proved below are indeed sharp worst-case gaps for their stated parameter regimes.
3. Path-merging phase — verified.
The parametrization
$$
\alpha=\frac{\rho}{(1-\rho)^2}
$$
has exactly one solution in $(0,1)$ for every $\alpha>0$.
The proposed path inverse satisfies the interior recurrence, endpoint conditions, and displayed normalization identity. The formulas were also checked symbolically for path sizes from one through six. These finite checks corroborate the general recurrence verification given in the output.
The endpoint diagonal formula is correct. Its second expression establishes strict decrease with component size; the position-dependent terms establish endpoint maximality.
The endpoint covariance and endpoint-pair score simplify as claimed. In particular, every isolated path endpoint score is strictly below $2(1-\rho)$.
The edge-removal comparison is valid: removing edges subtracts a positive semidefinite matrix from the precision matrix, and inversion reverses the positive definite order. The chosen pair then lies at the endpoints of an isolated subpath. Thus the comparison applies to every within-component pair.
Pairs in distinct components have zero cross-covariance, and their maximum scores are sums of endpoint diagonal entries. These scores exceed $2(1-\rho)$. Hence greedy must merge components until only one remains, and decreasing $v_s$ forces selection of the two smallest component sizes. Ties between equal sizes do not alter the size multiset.
The tridiagonal determinant recurrence and its solution give the stated $D_s$. Multiplication across components then proves the gap formula for $B\le m-1$.
4. Budgets $m$ and $m+1$ — verified.
For $m\ge3$, the endpoint score strictly increases with path size. Every other pair spans a shorter subpath, so the edge-removal bound proves that closing the full path is the unique next greedy choice.
The cycle determinant follows correctly from its Laplacian eigenvalues and the roots-of-unity product.
The periodized inverse kernel is valid: its shifts converge absolutely because $0<\rho<1$, and the displayed recurrence and normalization verify the precision equation. The resulting cycle pair score is correct.
The difference calculation proves strict increase up to maximum cyclic distance. All maximizing pairs therefore give the same determinant increment, regardless of which lexicographic tie is selected. The determinant lemma gives precisely the stated formula at $B=m+1$.
The special case $m=3$ correctly permits a repeated edge. The case $m=2$ is covered separately by its zero-gap result.
5. Unbounded-gap consequence — verified.
When $B\le\lfloor m/2\rfloor$, the component-merging rule produces a matching, giving the stated exact expression.
The limit
$$
\frac{D_s}{\alpha^{s-1}}\longrightarrow s
$$
is correct. Combining it with the number of components yields the displayed asymptotic expansion for fixed positive integer $B\le m-1$.
For $B<m-1$, the coefficient of $\log\alpha$ is positive, proving unboundedness as $\alpha$ increases. Restricting $\alpha$ to powers of two is compatible with rational inputs.
This is an unbounded-gap statement across varying $\alpha$; it does not supply the missing exact gap in the remaining regime.
6. All-budget formulas for $m\le6$ — verified.
For $m=2$, there is only one available pair, so the zero-gap statement is correct.
For $m=3$, the determinant expansion is correct. At a fixed current budget, comparing candidate increments reduces to comparing $B-a$, so greedy increments a minimum count. The balanced-count identity and the resulting formula with $\delta_B$ are correct.
The complete-layer reduction correctly distinguishes the constant direction from $\mathbf1^\perp$. This explains the factor $c_k^r$, rather than $c_k^m$, and validates both the determinant and inverse-score identities. Its use is conditional on parameter-independent complete layers, which the subsequent arguments establish for the claimed sizes.
For $m=4$, both cycle scores and the missing-edge precision calculation are correct. A present pair has strictly smaller score than the missing pair. All six listed prefix determinants were independently verified.
For $m=5,6$, exact recomputation confirms:
The certificate considers every pair, including already queried pairs, so it correctly accounts for the permission to repeat queries.
The principal-minor formula and Newton recurrence are valid. The explicit example at $m=6,s=6$ expands to the two coefficient vectors claimed. Consequently, the layer completion and all-budget gap formulas are established.
7. General upper bound — verified.
The contrast precision eigenvalues are positive and sum to $r+2\alpha k$. Averaging pair scores and applying Cauchy–Schwarz gives the stated lower bound on the selected scaled score.
The determinant increment is therefore bounded below as claimed. The product cancellation over the integer query indices yields the displayed sum over $j$. Subtracting from the continuous benchmark gives exactly the announced upper bound.
The endpoint $r=1$ gives an empty sum and correctly recovers zero gap for $m=2$.
8. Integral-design lower bound — correct after a minor notation clarification.
The precision eigenvalues lie in $[1,H]$ and have mean $c$. The stated strong-concavity inequality for $\log$ has the correct constant and direction. Summing cancels the linear terms.
The Frobenius-norm comparison correctly uses the two off-diagonal entries associated with each pair. The balancing argument for integer counts yields the minimum $s(M-s)/M$. Thus the final lower bound is correct.
Minor notation issue. In Section 2, $L_q$ denotes the variance-weighted Laplacian. In Section 6, the lower-bound calculation requires $L_q$ to denote the unweighted homogeneous count Laplacian, but this change is not stated.
This distinction matters literally. With $m=2$, $B=1$, and $\sigma_x^2=\sigma_1^2=2$, the actual gap is zero. Keeping the Section 2 definition of $L_q$ makes the first Frobenius-norm inequality assert a positive lower bound of $1/36$.
The minimum clarification is to define the Laplacian used in Section 6 explicitly as the unweighted count Laplacian, or give it a distinct symbol. This is a notation repair; the final bound and its mathematical argument survive it.
9. Outstanding target — major incompleteness.
USER_TASK requests the sharp worst-case greedy gap for general homogeneous integer-budget instances. The output supplies that gap only for:
For $m\ge7$ and $B>m+1$, it supplies bounds explicitly acknowledged to be non-sharp. Neither those bounds nor the proved small-size complete-layer patterns determine the requested value.
The prover accurately reports this limitation. There is no unsupported claim of a complete solution, but the assignment remains partially unresolved. Completing it requires a sharp characterization in the remaining regime; no expositional clarification alone will suffice.
The continuous subproblem is established as polynomial-time solvable. Under the requested JSON convention, however, an overall partial result must have continuous_status set to unresolved.
⟨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.