Answer: Polynomial-time solvable in the binary input model.
Theorem 18 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm~\ref{alg:fw_eg_mod} returns some $x$ with $\psi(x^*) - \psi(x) \leq \epsilon$ in $O\left(\frac{n^3 \kappa^2}{\epsilon}\right)$ many iterations. Each iteration can be implemented in $O(n^3)$ time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite supports of student types \(A_0\) and place types \(G_0\), positive rational masses \(\alpha_a\) and \(\beta_g\) summing to one on each side, and rational utilities \(u_{ag}\), compute an additive-\(\varepsilon\) approximation to the maximum of \(\sum_{a\in A_0}\alpha_a\log v_a(x)\), where \(x_{ag}\geq 0\), \(\sum_g x_{ag}=\alpha_a\), \(\sum_a x_{ag}=\beta_g\), and \(v_a(x)=\sum_g u_{ag}x_{ag}/\alpha_a\). Determine the running time in \(\tau_A=|A_0|\), \(\tau_G=|G_0|\), input bit length \(L\), accuracy \(\varepsilon\), and any necessary utility or mass conditioning parameters.
A society is given by its support: the list of types with positive mass, each mass encoded as a binary rational; support size counts listed types, not all possible types.
Let the nonempty student and place supports be \(A_0,G_0\), with sizes \(\tau_A,\tau_G\), and set \(m=\tau_G\). Their positive masses satisfy \(\sum_a\alpha_a=\sum_g\beta_g=1\).
Utilities are nonnegative binary rationals, normalized by \(\max_g u_{ag}=1\) for every student type; disagreement utilities are zero. Let \(L\) be the total input bit length, including rational accuracy \(0<\varepsilon<1\).
A feasible allocation satisfies \(x_{ag}\geq0\), \(\sum_gx_{ag}=\alpha_a\), and \(\sum_ax_{ag}=\beta_g\). Define \(v_a(x)=\alpha_a^{-1}\sum_gu_{ag}x_{ag}\) and \(F(x)=\sum_a\alpha_a\log v_a(x)\), using natural logarithms and \(\log0=-\infty\).
The computational problem is to find a feasible allocation with objective within additive \(\varepsilon\) of \(\max_xF(x)\).
Is this approximation problem solvable in polynomial time in \(m,\tau_A,\tau_G,L,\log(1/\varepsilon)\), or is it NP-hard? What is its running-time dependence on accuracy and any necessary utility or mass conditioning parameters?
For finite lists of \(n\) students and \(n\) places, conditional gradient achieves additive gap \(\delta\) for a quadratic extension of the log objective in \(O(n^3\kappa^2/\delta)\) iterations, each taking \(O(n^3)\) time, where \(\sum_j u_{ij}\geq1/\kappa\); a separate guarantee transfers accuracy to the original objective. [Source](https://arxiv.org/html/2106.02024v3)
The finite-list logarithmic problem also has polynomial-time approximation in input length and \(\log(1/\varepsilon)\). [Source](https://drops.dagstuhl.de/opus/volltexte/2022/15682/pdf/LIPIcs-ITCS-2022-86.pdf)
No result explicitly addressing this exact support-encoded mass formulation was identified in the literature search.
1. Result
The approximation problem is polynomial-time solvable in the binary input model. There is an algorithm returning a rational allocation that satisfies all feasibility constraints exactly and has additive objective gap at most \(\varepsilon\).
Write \(p=\tau_A\), \(\beta_{\min}=\min_g\beta_g\), and \(d=(p-1)(m-1)\). For \(p,m\geq2\), one implementation uses
\(\displaystyle O\!\left(d^2\left[\log(1/\varepsilon)+\log(1/\beta_{\min})+\log(pm+1)\right]\right)\)
ellipsoid iterations, each with polynomial bit cost. Consequently, total bit complexity is polynomial in \(p,m,L,\log(1/\varepsilon)\).
No additional numerical bound on the smallest positive utility or student mass is required. The displayed dependence on place-mass conditioning is logarithmic. This is a polynomial-time approximation result, without a claim of strong polynomiality or exact optimization.
The proof below works directly with the listed supports.
2. Existence and a bound on optimal utilities
Index the supports by \(a\in\{1,\ldots,p\}\) and \(g\in\{1,\ldots,m\}\). Define
\(\displaystyle b_{ag}=\alpha_a\beta_g,\qquad q_a=\sum_g\beta_g u_{ag},\qquad q=\min_a q_a.\)
The allocation \(b\) is feasible, and \(v_a(b)=q_a\). Every row has a supported place with utility \(1\), so
\(\displaystyle 1\geq q_a\geq\beta_{\min}>0.\)
Every feasible allocation satisfies \(v_a(x)\leq1\), hence \(F(x)\leq0\). The feasible transportation polytope is compact, and the extended objective is upper semicontinuous: each \(\log v_a\), with value \(-\infty\) at zero, is upper semicontinuous. Thus a maximum is attained. Since \(F(b)\) is finite and every \(\alpha_a\) is positive, every maximizer \(x^*\) has strictly positive utilities.
We will prove the stronger bound
\(\displaystyle v_a(x^*)\geq\frac{q_a}{2}\quad\text{for every }a.\)
First consider the relaxation with row and column sums bounded above by their prescribed masses. Any allocation \(y\) in this relaxation can be completed to an allocation satisfying equality. Indeed, let
\(\displaystyle R_a=\alpha_a-\sum_g y_{ag},\qquad C_g=\beta_g-\sum_a y_{ag},\qquad T=\sum_a R_a=\sum_g C_g.\)
If \(T>0\), add \(R_aC_g/T\) to entry \(y_{ag}\); if \(T=0\), all equalities already hold. Nonnegative utilities imply that completion cannot decrease the objective. Therefore \(x^*\) also maximizes the objective over this relaxation.
Set \(c_{ag}=u_{ag}/v_a(x^*)\). For any relaxed feasible \(y\), the utilities along \((1-t)x^*+ty\) remain positive for \(t<1\). Optimality gives the right derivative inequality
\(\displaystyle 0\geq\left.\frac{d}{dt}F((1-t)x^*+ty)\right|_{t=0} =\sum_{a,g}c_{ag}(y_{ag}-x^*_{ag}).\)
Consequently, \(x^*\) maximizes the linear objective \(\sum_{a,g}c_{ag}y_{ag}\) over the relaxation. Its value is
\(\displaystyle \sum_{a,g}c_{ag}x^*_{ag}=\sum_a\alpha_a=1.\)
This linear program is feasible and bounded. Its dual is feasible, for example by choosing \(r_a=\max_g c_{ag}\) and \(s_g=0\). Linear-programming strong duality therefore supplies optimal dual variables satisfying
\(\displaystyle r_a,s_g\geq0,\qquad r_a+s_g\geq c_{ag},\qquad \sum_a\alpha_a r_a+\sum_g\beta_g s_g=1.\)
Complementary slackness gives equality \(r_a+s_g=c_{ag}\) whenever \(x^*_{ag}>0\). Summing these equalities over a row yields
\(\displaystyle \alpha_a r_a+\sum_g x^*_{ag}s_g =\sum_g x^*_{ag}c_{ag}=\alpha_a.\)
Thus \(r_a\leq1\). Also \(\sum_g\beta_gs_g\leq1\), since all dual variables are nonnegative. Multiplying the dual inequalities by \(\beta_g\) and summing gives
\(\displaystyle \frac{q_a}{v_a(x^*)} =\sum_g\beta_g c_{ag} \leq r_a+\sum_g\beta_gs_g\leq2.\)
This proves the claimed utility bound.
3. A bounded convex program in independent coordinates
If \(p=1\) or \(m=1\), the feasible allocation is unique and can be returned directly. Henceforth assume \(p,m\geq2\), so \(d\geq1\).
Relabel students so that \(\alpha_p=\max_a\alpha_a\). Then \(\alpha_p\geq1/p\). Use per-student allocation fractions \(y_{ag}=x_{ag}/\alpha_a\), and introduce independent coordinates \(z_{ag}\) for \(a<p\), \(g<m\). Reconstruct the remaining fractions by
\(\displaystyle y_{ag}=z_{ag}\quad(a<p,\ g<m),\qquad y_{am}=1-\sum_{g<m}z_{ag}\quad(a<p),\)
\(\displaystyle y_{pg}=\frac{\beta_g-\sum_{a<p}\alpha_a z_{ag}}{\alpha_p}\quad(g<m),\qquad y_{pm}=1-\sum_{g<m}y_{pg}.\)
These formulas enforce all row and column equalities. Thus \(x_{ag}=\alpha_a y_{ag}(z)\) is feasible exactly when every reconstructed fraction is nonnegative.
Define the rational polytope
\(\displaystyle K=\left\{z:\ y_{ag}(z)\geq0\ \text{for all }a,g,\quad v_a(z):=\sum_g u_{ag}y_{ag}(z)\geq q_a/4\ \text{for all }a\right\}.\)
It has \(pm+p\) affine inequalities, with coefficients of polynomial encoding length. Section 2 shows that every original maximizer belongs to \(K\). Therefore minimizing
\(\displaystyle f(z)=-\sum_a\alpha_a\log v_a(z)\)
over \(K\) is equivalent to the original optimization problem.
On \(K\), utilities lie between \(q_a/4\) and \(1\). Hence
\(\displaystyle 0\leq f(z)\leq\log(4/\beta_{\min})\leq H,\qquad H:=2+\left\lceil\log_2(1/\beta_{\min})\right\rceil.\)
The integer \(H\) can be computed using exact rational comparisons with powers of two.
Membership in \(K\), together with a separating affine inequality when membership fails, is computable by rational arithmetic. At a rational point of \(K\), the gradient is also rational:
\(\displaystyle \frac{\partial f}{\partial z_{ag}} =\alpha_a\left( -\frac{u_{ag}-u_{am}}{v_a(z)} +\frac{u_{pg}-u_{pm}}{v_p(z)} \right),\qquad a<p,\ g<m.\)
Its encoding length is polynomial in the input length and the queried point’s encoding length.
4. An explicit ball of nearly optimal points
Let \(z^0_{ag}=\beta_g\). Its reconstructed fractions are \(y_{ag}(z^0)=\beta_g\) for every student.
For a perturbation \(w\), each reconstructed fraction changes by at most
\(\displaystyle |y_{ag}(z^0+w)-y_{ag}(z^0)|\leq pd\,\|w\|_2.\)
Here is a verification of that bound. The coefficient norms for ordinary entries and ordinary last-column entries are \(1\) and \(\sqrt{m-1}\). For the pivot student, they are bounded respectively by
\(\displaystyle \alpha_p^{-1}\sqrt{\sum_{a<p}\alpha_a^2}\leq p,\qquad \alpha_p^{-1}\sqrt{(m-1)\sum_{a<p}\alpha_a^2}\leq p\sqrt{m-1}.\)
All four bounds are at most \(pd\).
Set
\(\displaystyle r_0=\frac{\beta_{\min}}{4pmd}.\)
If \(\|w\|_2\leq r_0\), every fraction changes by at most \(\beta_{\min}/(4m)\), so all fractions remain positive. Moreover,
\(\displaystyle |v_a(z^0+w)-q_a| \leq\sum_g u_{ag}|y_{ag}(z^0+w)-\beta_g| \leq\beta_{\min}/4.\)
Since \(q_a\geq\beta_{\min}\), the perturbed utility is at least \(3q_a/4\). Therefore the Euclidean ball \(B(z^0,r_0)\) lies in \(K\).
An outer radius is also explicit. For \(z\in K\), each ordinary row has nonnegative entries summing to at most \(1\). Thus
\(\displaystyle \|z\|_2^2\leq p-1,\qquad K\subseteq B(0,R),\quad R:=p.\)
Let \(z^*\) minimize \(f\) over \(K\), and write \(f^*=f(z^*)\). Define
\(\displaystyle \theta=\frac{\varepsilon}{4H},\qquad z^\theta=(1-\theta)z^*+\theta z^0,\qquad r=\theta r_0=\frac{\varepsilon\beta_{\min}}{16Hpmd}.\)
Every point in \(B(z^\theta,r)\) has the form \((1-\theta)z^*+\theta y\), with \(y\in B(z^0,r_0)\). Convexity of \(K\) and \(f\), and the bounds \(0\leq f\leq H\), imply
\(\displaystyle f((1-\theta)z^*+\theta y) \leq(1-\theta)f^*+\theta H \leq f^*+\varepsilon/4.\)
Hence the sublevel set
\(\displaystyle S=\{z\in K:\ f(z)\leq f^*+\varepsilon/4\}\)
contains a ball of radius \(r\).
5. Ellipsoid algorithm and correctness
We use the standard rational central-cut ellipsoid method. Starting from a ball of radius \(R\), it maintains containment of any fixed target set retained by all cuts. With polynomially many precision bits, its volume decreases by a factor at most \(\exp(-1/(5d))\) per iteration. Thus \(O(d^2\log(R/r))\) cuts suffice to make its volume smaller than that of a radius-\(r\) ball. These containment, volume, and bit-complexity properties are proved in [Grötschel–Lovász–Schrijver, Section 3.2](https://www.mpi-inf.mpg.de/fileadmin/inf/d1/ellipsoid-lovasz.pdf). In dimension one, interval bisection gives the same required guarantee.
At each rational center \(c\):
\(\nabla f(c)\cdot(z-c)\leq0\).
Run sufficiently many iterations to obtain the volume bound above.
Suppose, for contradiction, that every recorded center satisfies \(f(c)>f^*+\varepsilon/2\). Every feasibility cut retains \(S\). Every objective cut also retains \(S\), because for \(z\in S\), convexity gives
\(\displaystyle \nabla f(c)\cdot(z-c)\leq f(z)-f(c)<-\varepsilon/4.\)
Consequently, the final ellipsoid would still contain \(S\), including its radius-\(r\) ball. This contradicts the final volume bound. Therefore some recorded feasible center satisfies
\(\displaystyle f(c)\leq f^*+\varepsilon/2.\)
Approximate each recorded objective value to absolute error at most \(\varepsilon/8\), and choose a center \(\widehat z\) with the smallest approximate value. Comparing its approximate value with that of the best recorded center gives
\(\displaystyle f(\widehat z)\leq\min_{\text{recorded }c}f(c)+\varepsilon/4 \leq f^*+3\varepsilon/4.\)
The rational allocation \(\widehat x_{ag}=\alpha_a y_{ag}(\widehat z)\) satisfies all feasibility constraints exactly and obeys
\(\displaystyle F(x^*)-F(\widehat x)\leq3\varepsilon/4<\varepsilon.\)
6. Bit complexity and conditioning
All cuts use exact rational gradients or affine constraints. Logarithms are needed only to select the output.
For completeness, logarithms of positive rationals can be approximated in polynomial bit time. Write \(h=2^j w\), where \(1\leq w<2\). Then
\(\displaystyle \log h=j\log2+\log w,\qquad \log w=2\sum_{k=0}^{\infty}\frac{t^{2k+1}}{2k+1},\quad t=\frac{w-1}{w+1}\in[0,1/3].\)
Truncating after \(K\) terms has error at most \(3^{-2K}\). The same series computes \(\log2\). Choosing accuracy to account for the factor \(j\) requires polynomially many terms in the rational’s bit length and the requested accuracy bits. Since \(\sum_a\alpha_a=1\), approximating each \(\log v_a\) to error \(\varepsilon/8\) also approximates the weighted objective to that error.
The iteration bound is
\(\displaystyle O\!\left(d^2\log\frac{R}{r}\right) =O\!\left(d^2\log\frac{16Hp^2md}{\varepsilon\beta_{\min}}\right).\)
Using \(d\leq pm\) and the definition of \(H\) gives the bound stated in Section 1. The rational ellipsoid centers have polynomial encoding length; therefore all constraint checks, gradient calculations, ellipsoid updates, and objective evaluations have polynomial bit cost.
A positive binary rational encoded within \(L\) bits is at least \(2^{-O(L)}\). In particular, \(\log(1/\beta_{\min})=O(L)\). The total running time is consequently polynomial in the requested parameters.
The conditioning conclusions are:
The finite-list polynomial-accuracy result is consistent with this conclusion. [Hosseini and Vazirani](https://drops.dagstuhl.de/opus/volltexte/2022/15682/pdf/LIPIcs-ITCS-2022-86.pdf) discuss ellipsoid approximation polynomial in input size and accuracy bits. Clearing denominators and expanding the present supports into individual students and places can create exponentially many individuals, so direct expansion does not establish the support-encoded bound.
The quoted conditional-gradient guarantee concerns a quadratic extension and requires a separate accuracy-transfer argument. [Panageas, Tröbst, and Vazirani, Theorem 24 and Lemma 23](https://arxiv.org/html/2106.02024v3) give those guarantees. The proof here supplies polynomial dependence on accuracy bits directly for the original weighted logarithmic objective.
⟨structured verdict parsed — rendered above⟩
The prover resolves the support-encoded approximation problem. The argument is correct, including its polynomial bit complexity and logarithmic dependence on accuracy. I found no major or minor mathematical issues requiring repair.
1. Scope and assumptions
The proof works with the listed types directly. It does not expand rational masses into individual students or places.
The normalization is used over the supported places: every student row has some supported place with utility \(1\). This matches the intended formulation of the task. Positivity of every listed mass and the normalization of both total masses are used correctly.
The cases \(p=1\) and \(m=1\) are correctly separated: the marginal constraints determine a unique feasible allocation.
2. Existence and positive optimal utilities
The product allocation \(b_{ag}=\alpha_a\beta_g\) satisfies both marginal constraints. Its utilities satisfy
\[
\beta_{\min}\leq q_a\leq1.
\]
Thus its objective is finite.
The feasible transportation polytope is nonempty and compact. The extended logarithmic objective is upper semicontinuous, including at zero utility. Consequently, a maximum is attained. Because a finite objective is feasible and every weight \(\alpha_a\) is positive, no maximizer can have a zero utility.
These steps correctly handle the logarithm’s boundary singularity.
3. The optimal-utility lower bound
The relaxation and completion argument are valid. Row and column deficits are nonnegative and have the same total \(T\). For \(T>0\), the proposed addition has precisely those deficits as its marginals. For \(T=0\), every deficit vanishes. Nonnegative utilities ensure that completion cannot reduce the objective.
The derivative computation is correct:
\[
\left.\frac{d}{dt}F((1-t)x^*+ty)\right|_{t=0}
=\sum_{a,g}\frac{u_{ag}}{v_a(x^*)}(y_{ag}-x^*_{ag}).
\]
The factors \(\alpha_a\) cancel as claimed. Positive utilities at \(x^*\) justify differentiating at zero, even when \(y\) has zero utilities.
The resulting linear program is feasible and bounded. Its stated dual has the correct signs, constraints, and objective. The exhibited dual solution establishes dual feasibility, so finite-dimensional linear-programming strong duality and complementary slackness apply.
The subsequent calculations correctly establish
\[
r_a\leq1,\qquad
\sum_g\beta_gs_g\leq1,\qquad
\frac{q_a}{v_a(x^*)}\leq2.
\]
Therefore the claimed bound \(v_a(x^*)\geq q_a/2\) holds for every student type. No smallest-student-mass assumption is introduced.
4. Independent coordinates and the restricted program
The reconstruction formulas enforce all row and column equalities, including the last column. Nonnegativity of all reconstructed fractions is exactly the remaining feasibility condition.
The additional utility constraints defining \(K\) retain every original maximizer by the preceding bound. Conversely, every point in \(K\) gives an original feasible allocation. Thus minimizing \(f\) over \(K\) has exactly the required optimal value.
The objective bound
\[
0\leq f(z)\leq\log(4/\beta_{\min})\leq H
\]
is valid. The displayed gradient is also correct, including the pivot-row contribution and its sign.
The affine coefficients and rational gradients have polynomial encoding length relative to the input and queried point.
5. Interior and near-optimal balls
All four coefficient-norm bounds in Section 4 check out. Since \(p,m\geq2\) and \(d=(p-1)(m-1)\), their replacement by the common upper bound \(pd\) is valid.
With the stated \(r_0\), each fraction changes by at most \(\beta_{\min}/(4m)\). Hence all fractions remain positive, and each utility changes by at most \(\beta_{\min}/4\). The resulting bound \(v_a\geq3q_a/4\) verifies that the whole ball lies in \(K\).
The outer-radius calculation is correct: nonnegative entries in each ordinary row sum to at most one, yielding \(\|z\|_2^2\leq p-1\).
The interpolation argument establishes that the entire radius-\(r\) ball around \(z^\theta\) belongs to the near-optimal sublevel set. It uses only the already established convexity and objective bounds. The constants in \(\theta\) and \(r\) are consistent.
6. Ellipsoid invocation and termination
The cited source supports the particular properties used here. In Section 3.2, the rational central-cut construction compensates for rounding; Lemmas 3.2.8–3.2.10 establish bounded encoding lengths, containment, and volume decrease by at most \(\exp(-1/(5d))\) per update. These are properties of the updates, so the proof may use them with its adaptive feasibility and objective cuts. [Grötschel–Lovász–Schrijver, Section 3.2](https://www.mpi-inf.mpg.de/fileadmin/inf/d1/ellipsoid-lovasz.pdf)
The hypotheses needed for those properties are supplied: a known enclosing ball, rational centers, polynomially computable rational nonzero cut normals, and a prescribed finite iteration budget. The zero-gradient case is handled separately, and dimension one is correctly assigned to interval bisection.
Under the contradiction assumption, every objective cut retains \(S\), because
\[
\nabla f(c)\cdot(z-c)\leq f(z)-f(c)<-\varepsilon/4.
\]
Feasibility cuts retain all of \(K\). Therefore the containment-versus-volume contradiction is valid.
The algorithm does not need to know \(f^*\), \(z^*\), or the location of the near-optimal ball. Those quantities occur only in its correctness analysis.
7. Output selection and accuracy
Approximating each recorded objective to absolute error \(\varepsilon/8\) loses at most \(\varepsilon/4\) when selecting the smallest approximation. Combined with the guaranteed recorded gap \(\varepsilon/2\), this yields the stated gap \(3\varepsilon/4\).
Every recorded candidate belongs to \(K\) by exact rational checks. Reconstruction therefore produces a rational allocation satisfying all original feasibility constraints exactly.
The logarithm series and truncation bound are valid. Accounting for the multiplier \(j\) in \(j\log2\) requires only polynomially many accuracy bits. Since the positive weights sum to one, the per-logarithm error bound transfers correctly to the weighted objective.
8. Running time and conditioning
The final iteration expression follows correctly from the two radii:
\[
O\!\left(d^2\log\frac{16Hp^2md}{\varepsilon\beta_{\min}}\right).
\]
Its simplification to the Section 1 bound is valid. Polynomial encoding lengths of the ellipsoid centers make all rational checks, gradients, updates, and objective evaluations polynomial-time operations.
A positive binary rational of input encoding length at most \(L\) has logarithmic inverse magnitude bounded by \(O(L)\). Consequently, the explicit place-mass dependence remains polynomial in the binary input size.
The conclusions concerning conditioning are justified:
The contextual literature statements are consistent with the cited passages, but the support-encoded conclusion rests on the proof audited above. [Hosseini–Vazirani](https://drops.dagstuhl.de/opus/volltexte/2022/15682/pdf/LIPIcs-ITCS-2022-86.pdf), [Panageas–Tröbst–Vazirani, Lemma 23 and Theorem 24](https://arxiv.org/html/2106.02024v3)
No additional clarification is needed to make the argument verifiable.
⟨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.