Answer: The problem admits an additive approximation scheme, with exactly feasible rational output and running time \(\operatorname{poly}(m,\tau,L)\).
Theorem 5.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere is no FPTAS for {\sc C-KP}, unless P = NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(T\) of device types \(t=(d_t,v_t)\), with rational masses \(\mu_t\ge 0\) summing to \(1\), and per-capita capacity \(c\), choose served masses \(y_t\in[0,\mu_t]\). Each served unit of mass receives its full demand \(d_t\), and each unserved unit receives none. Compute an allocation with welfare within additive \(\epsilon\) of the maximum \(\sum_{t\in T}y_tv_t\), subject to \(\left|\sum_{t\in T}y_td_t\right|\le c\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) device types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type is \(t=(d_t,v_t)\), where \(d_t=a_t+\mathrm{i}b_t\), \(a_t,b_t\in\mathbb{Q}_{\geq0}\), and \(v_t\in\mathbb{Q}_{>0}\). The per-capita capacity is \(c\in\mathbb{Q}_{>0}\), and the additive tolerance is \(\epsilon\in\mathbb{Q}_{>0}\); values have no upper normalization.
Choose served masses \(0\leq y_t\leq\mu_t\): each served device receives its full demand, and each unserved device receives nothing. Feasibility requires \(\left|\sum_{t\in T}y_td_t\right|\leq c\), with no capacity violation permitted.
Let \(\mathrm{OPT}=\max\{\sum_{t\in T}y_tv_t:0\leq y_t\leq\mu_t,\ |\sum_{t\in T}y_td_t|\leq c\}\). The computational problem is to output feasible rational served masses with welfare at least \(\mathrm{OPT}-\epsilon\).
Let \(m=2\) be the demand dimension and \(L\) the total binary input length, including \(\epsilon\).
Does this problem admit an additive approximation scheme running in \(\operatorname{poly}(m,\tau,L,\max\{1,1/\epsilon\})\), or is such a scheme impossible unless \(\mathrm{P}=\mathrm{NP}\)?
For indivisible devices with first-quadrant demands, no FPTAS exists unless \(\mathrm{P}=\mathrm{NP}\). [Yu and Chau](https://arxiv.org/pdf/1205.2285)
Fractional complex-demand knapsack is explicitly considered in [Najy's thesis](https://khazna.ku.ac.ae/ws/portalfiles/portal/6811459/file), alongside relative approximation schemes for packing problems; no guarantee with exactly the additive error and binary running time stated here was verified.
Result. The problem admits the requested additive approximation scheme. In fact, it can be solved in time \(\operatorname{poly}(m,\tau,L)\), with exactly feasible rational output. The proof below accounts explicitly for binary precision and unbounded values.
1. Normalize the served masses.
Write \(n=\tau\), and define
\(x_t=y_t/\mu_t\), \(w_t=\mu_tv_t\), and the rational matrix \(B\in\mathbb{Q}^{2\times n}\) whose column indexed by \(t\) is \((\mu_ta_t,\mu_tb_t)^{\mathsf T}\).
The problem becomes maximizing \(w^{\mathsf T}x\) over
\(K=\{x\in[0,1]^n:\|Bx\|_2\leq c\}\).
This change of variables preserves feasibility and welfare exactly. The set \(K\) is nonempty, compact, and convex: it contains zero and is the intersection of a box with the inverse image of a closed Euclidean ball under a linear map. Consequently, an optimizer \(x^*\in K\) exists.
Set \(W=\sum_t w_t\). Since all \(w_t\) are positive, \(0\leq\mathrm{OPT}\leq W\). If \(\epsilon\geq W\), outputting zero solves the problem. Henceforth assume \(0<\epsilon<W\).
2. The feasibility theorem used.
We use the following standard consequence of the rational ellipsoid method:
Given a closed convex set \(C\subseteq\mathbb{R}^n\), an enclosing radius \(R>0\), a radius \(r>0\), and an exact rational separation oracle, there is an algorithm that either returns a rational point in \(C\), or correctly reports that \(C\) contains no Euclidean ball of radius \(r\). Its binary running time is polynomial in the dimension, the encodings of \(R,r\), and the separation-oracle complexity.
Here the oracle must certify membership exactly or return a nonzero rational vector \(h\) with \(h^{\mathsf T}z\leq h^{\mathsf T}x\) for every \(z\in C\), where \(x\) is the queried point.
For completeness, the exact-membership formulation follows from the rational central-cut ellipsoid algorithm: use the exact oracle for its membership decisions and run until its enclosing ellipsoid has volume at most \((r/n)^n\). A radius-\(r\) ball contains a cube of volume \((2r/n)^n\), so such termination certifies the claimed absence of a ball. The algorithm’s rational rounding preserves containment and uses polynomial-length numbers. These properties are proved in Theorem 3.2.1 and its implementation analysis in [Grötschel–Lovász–Schrijver, Chapter 3](https://www.mpi-inf.mpg.de/fileadmin/inf/d1/ellipsoid-lovasz.pdf). In dimension one, interval halving gives the same conclusion.
3. Construct an exact rational separation oracle.
For any rational welfare target \(q\), define
\(K_q=\{x\in[0,1]^n:\|Bx\|_2\leq c,\ w^{\mathsf T}x\geq q\}\).
This set is closed and convex, and \(K_q\subseteq K\subseteq\{x:\|x\|_2\leq n\}\). Thus \(R=n\) is a valid enclosing radius.
At a rational query point, the box and welfare inequalities can be checked exactly. A violated inequality directly supplies a rational separating hyperplane.
The capacity check is also exact: compare the rational quantities \(\|Bx\|_2^2\) and \(c^2\). If \(\|Bx\|_2^2>c^2\), let \(h=B^{\mathsf T}Bx\). For every \(z\in K_q\), expansion of the squared norm gives
\(\|Bz\|_2^2=\|Bx\|_2^2+2h^{\mathsf T}(z-x)+\|B(z-x)\|_2^2\).
Consequently,
\(2h^{\mathsf T}(z-x)\leq c^2-\|Bx\|_2^2<0\).
Thus \(h\) gives a valid separating cut. It is nonzero because \(h^{\mathsf T}x=\|Bx\|_2^2>c^2>0\).
All these operations use rational arithmetic in polynomial time. Cut normals can be normalized by their largest absolute coordinate, also using rational arithmetic. In particular, the oracle certifies capacity feasibility without computing square roots.
4. Prove that sufficiently low welfare targets contain a ball.
Define the rational quantities
\(M=\max\{1,\sum_{j=1}^{2}\sum_t B_{jt}\}\),
\(s=\min\{1/2,c/(4M)\}\),
\(x^0=s\mathbf{1}\).
Nonnegativity of the entries of \(B\) gives \(\|B\mathbf{1}\|_2\leq M\). It also gives, for every \(u\in\mathbb{R}^n\),
\(\|Bu\|_2\leq\sum_t\|B_{\cdot t}\|_2|u_t|\leq M\|u\|_2\).
Hence \(\|Bx^0\|_2\leq c/4\).
Now set
\(\eta=\epsilon/8,\qquad \alpha=\eta/W,\qquad r=\alpha s/2\).
These are positive rational numbers, with \(\alpha<1/8\). We claim that
\(q\leq\mathrm{OPT}-2\eta\quad\Longrightarrow\quad K_q\text{ contains a Euclidean ball of radius }r.\)
To prove this, define the possibly irrational center
\(z=(1-\alpha)x^*+\alpha x^0\).
Every coordinate satisfies \(\alpha s\leq z_t\leq1-\alpha s\), since \(s\leq1/2\). Moreover,
\(\|Bz\|_2\leq(1-\alpha)c+\alpha c/4=c-3\alpha c/4\),
and, using \(w^{\mathsf T}x^0\geq0\) and \(\mathrm{OPT}\leq W\),
\(w^{\mathsf T}z\geq(1-\alpha)\mathrm{OPT}\geq\mathrm{OPT}-\eta\).
Consider any \(u\) with \(\|u\|_2\leq r\). Since \(|u_t|\leq r=\alpha s/2\), the point \(z+u\) remains in the box. For capacity, \(Ms\leq c/4\) implies
\(\|B(z+u)\|_2\leq c-3\alpha c/4+Mr\leq c-5\alpha c/8<c\).
For welfare, positivity of the weights implies
\(|w^{\mathsf T}u|\leq W\|u\|_2\leq Wr=\eta s/2\leq\eta/4\).
Therefore
\(w^{\mathsf T}(z+u)\geq\mathrm{OPT}-5\eta/4\geq q+3\eta/4\).
The entire closed radius-\(r\) ball centered at \(z\) belongs to \(K_q\), proving the claim. The algorithm needs only the rational radius \(r\); it does not need to know \(z\) or \(x^*\).
5. Search while accounting for inconclusive feasibility tests.
Maintain rational bounds \(\ell,u\) and a rational feasible witness \(\widehat{x}\), with invariants
\(w^{\mathsf T}\widehat{x}\geq\ell,\qquad \ell\leq\mathrm{OPT}\leq u\).
Initially use \(\ell=0\), \(u=W\), and \(\widehat{x}=0\).
While \(u-\ell>\epsilon\), set \(q=(\ell+u)/2\) and apply the feasibility theorem to \(K_q\), using \(R=n\) and the radius \(r\) constructed above.
Both updates preserve the invariants. In the second case, no assertion that \(K_q\) is empty is required.
If the old interval width is \(D>\epsilon\), the new width is at most
\(D/2+2\eta=D/2+\epsilon/4<3D/4\).
Thus the search terminates after \(O(1+\log(W/\epsilon))\) iterations. At termination,
\(w^{\mathsf T}\widehat{x}\geq\ell\geq\mathrm{OPT}-\epsilon\).
Output \(\widehat{y}_t=\mu_t\widehat{x}_t\). These masses are rational, satisfy all box bounds, and meet the original capacity constraint exactly.
6. Verify the binary running time.
Products and sums defining \(B,w,W,M,s,\alpha,r\) have polynomial encoding length. Crucially, large values enter through their binary encodings.
More explicitly, each positive input rational lies between \(2^{-L}\) and \(2^L\). Because the masses sum to one,
\(W\leq2^L,\qquad M\leq2^{L+1}\).
It follows that
\(s\geq2^{-2L-3},\qquad \alpha\geq2^{-2L-3},\qquad r\geq2^{-4L-7}\).
Hence \(\log(n/r)=O(L+\log n)\), and \(\log(W/\epsilon)=O(L)\). The search targets have polynomial encoding length, and every ellipsoid call has polynomial binary running time and returns a polynomial-length rational witness.
The total running time is therefore \(\operatorname{poly}(\tau,L)\) for \(m=2\), which satisfies the requested bound. The same argument works for an explicitly supplied nonnegative rational matrix with \(m\) rows, giving \(\operatorname{poly}(m,\tau,L)\).
The indivisible-device obstruction concerns subset selection, as formulated by [Yu and Chau](https://arxiv.org/pdf/1205.2285). The continuously variable served masses here yield the convex sets used throughout this proof. [Najy’s thesis, Section 3.1](https://khazna.ku.ac.ae/ws/portalfiles/portal/6811459/file) likewise formulates fractional complex-demand knapsack as a convex quadratic program; the argument above establishes the specific additive, binary-time, exactly feasible guarantee.
⟨structured verdict parsed — rendered above⟩
The argument establishes the requested polynomial-time additive approximation with exactly feasible rational output. I found no mathematical or complexity gap. There is one minor citation error: the thesis passage is in Section 3.4.2, not Section 3.1.
Every mass satisfies \(\mu_t>0\), so \(x_t=y_t/\mu_t\) gives a bijection between the original box constraints and \(x\in[0,1]^n\). The definitions of \(B\) and \(w\) preserve both total demand and welfare exactly.
The feasible set \(K\) is nonempty, compact, and convex. The linear objective therefore attains its maximum. Positivity of the weights gives \(0\leq\mathrm{OPT}\leq W\). When \(\epsilon\geq W\), the zero output is feasible and satisfies the required guarantee, including equality.
The cited theorem itself permits approximate membership. However, its algorithm accepts a center when the oracle accepts it. Using the exact oracle stipulated by the prover therefore makes every returned point an actual member of the set. The cited analysis also establishes containment, volume contraction, and polynomial encoding lengths despite rational rounding. This supports the prover’s stated consequence. [Grötschel–Lovász–Schrijver, Theorem 3.2.1 and its implementation analysis](https://www.mpi-inf.mpg.de/fileadmin/inf/d1/ellipsoid-lovasz.pdf).
The volume threshold is sufficient: a radius-\(r\) ball contains the stated cube of volume \((2r/n)^n\), which is strictly larger than \((r/n)^n\). An enclosing ellipsoid below the latter threshold consequently certifies absence of such a ball.
The application satisfies the hypotheses: \(K_q\) is closed and convex, lies in the origin-centered radius-\(n\) ball, and has the exact rational oracle verified below. Empty or lower-dimensional sets do not invalidate the procedure, because its failure outcome concerns absence of a ball, not emptiness. The separately stated interval-halving treatment covers \(n=1\).
Box and welfare violations give rational linear cuts directly. The squared capacity test uses rational arithmetic and has no numerical ambiguity.
For a capacity violation, the squared-norm expansion is correct. Since the final squared term is nonnegative, it implies
\(2h^{\mathsf T}(z-x)\leq c^2-\|Bx\|_2^2<0\)
for every feasible \(z\). Thus the proposed central cut contains \(K_q\) and separates the queried point.
The identity \(h^{\mathsf T}x=\|Bx\|_2^2>c^2>0\) proves that \(h\neq0\). Normalizing by the largest absolute coordinate preserves the cut and is rational. Oracle computations have polynomial bit complexity in the input and query encoding lengths.
Nonnegativity of \(B\) supports both \(\|B\mathbf1\|_2\leq M\) and the stated operator bound \(\|Bu\|_2\leq M\|u\|_2\).
The definition of \(s\) ensures \(0<s\leq1/2\) and \(Ms\leq c/4\), including when the minimum selects \(1/2\). Hence \(x^0\) has the claimed capacity slack.
The assumption \(0<\epsilon<W\) gives \(0<\alpha<1/8\). For the center \(z\), the coordinate margins, capacity estimate, and welfare estimate all follow from the stated convex combination.
For every \(\|u\|_2\leq r\):
Thus welfare throughout the ball is at least \(\mathrm{OPT}-5\eta/4\). Under \(q\leq\mathrm{OPT}-2\eta\), this is at least \(q+3\eta/4\). The entire closed ball belongs to \(K_q\).
An irrational center causes no problem: the feasibility procedure needs the rational radius, not an encoding of the center.
A returned member of \(K_q\) supplies the required feasible witness and justifies increasing \(\ell\) to \(q\).
If no radius-\(r\) ball exists, the contrapositive of the interior-ball claim gives \(q>\mathrm{OPT}-2\eta\). Consequently, replacing \(u\) by \(q+2\eta\) preserves the upper bound on \(\mathrm{OPT}\).
When the old width is \(D>\epsilon\), the new width is at most \(D/2+\epsilon/4<3D/4\). This verifies termination and the stated iteration bound. At termination, the witness has welfare at least \(\mathrm{OPT}-\epsilon\).
Multiplying its coordinates by the positive rational masses restores the original variables with exact feasibility and unchanged welfare.
The rational products and sums defining the parameters have polynomial encoding length.
For \(m=2\), mass normalization gives \(W\leq2^L\) and \(M\leq2^{L+1}\). Together with \(c,\epsilon\geq2^{-L}\), these imply the displayed lower bounds on \(s\), \(\alpha\), and \(r\); the constants are conservative.
Therefore \(\log(n/r)=O(L+\log n)\) and \(\log(W/\epsilon)=O(L)\). Search targets acquire only polynomially many additional bits through midpoint updates. The ellipsoid calls and their rational witnesses consequently have polynomial binary complexity.
The extension to an explicitly supplied nonnegative matrix with \(m\) rows also preserves polynomial encoding lengths and the same geometric estimates. The fixed-two-row numerical bound on \(M\) need not be reused unchanged for that extension.
Yu and Chau formulate an indivisible subset-selection problem and establish its FPTAS obstruction. That does not contradict this proof for continuous served masses. [Yu and Chau](https://arxiv.org/pdf/1205.2285).
The thesis does formulate fractional complex-demand knapsack with a linear objective, box constraints, and a quadratic capacity constraint. However, the passage appears in Section 3.4.2, on printed pages 21–22, rather than Section 3.1. [Najy’s thesis](https://khazna.ku.ac.ae/ws/portalfiles/portal/6811459/file).
Minimum repair: correct the subsection reference. No mathematical repair is needed.
⟨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.