Answer: Polynomial-time exactly solvable; therefore admits a feasible PTAS.
Theorem 4.10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any ϵ, δ > 0 there is a (1 −3ϵ)- socially efficient truthful mechanism for multiCKP[0, π 2 −δ].
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational distribution \(\mu\) over customer types, where each type has a finite menu \(D_t\) of power demands and valuations \(v_t(d)\), with demands in the positive quadrant and angles at most \(\pi/2-\delta\), choose masses \(x_{t,d}\ge 0\) maximizing \(\sum_t\sum_{d\in D_t}x_{t,d}v_t(d)\), subject to \(\sum_{d\in D_t}x_{t,d}=\mu_t\) for every type and \(\left|\sum_t\sum_{d\in D_t}x_{t,d}d\right|\le c\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational \(\mu_t\), with \(\sum_t\mu_t=1\). The parameter \(\tau\) is the support size, not the number of possible types.
Each type has an explicitly listed finite menu \(D_t\) containing \(0\), with \(v_t(0)=0\). Capacity \(c>0\), demand coordinates, and nonnegative valuations are binary rationals. Fix \(0<\delta<\pi/2\).
Every nonzero demand \(d\) has nonnegative coordinates, \(\lVert d\rVert_2\le c\), and \(\arg(d)\in[0,\pi/2-\delta]\). Valuations are monotone on each menu under coordinatewise magnitude comparison between demands having the same coordinate signs, with \(0\) below every demand.
An allocation consists of real masses \(x_{t,d}\ge0\) satisfying \(\sum_{d\in D_t}x_{t,d}=\mu_t\) for every type and \(\lVert\sum_t\sum_{d\in D_t}x_{t,d}d\rVert_2\le c\). Its welfare is \(\sum_t\sum_{d\in D_t}x_{t,d}v_t(d)\); let \(\mathrm{OPT}\) be the maximum welfare.
Let \(m=\sum_t|D_t|\) and let \(L\) be the total binary input length. State running times in \(m,\tau,L\) and the accuracy parameter \(\varepsilon\), treating \(\delta\) as fixed.
Does this mass-allocation problem admit a PTAS returning a feasible allocation of welfare at least \((1-\varepsilon)\mathrm{OPT}\) for every \(0<\varepsilon<1\), or is achieving this guarantee NP-hard for some fixed \(\varepsilon\)?
The discrete multi-minded complex-demand knapsack problem in this angular domain admits a truthful PTAS with welfare guarantee \((1-3\varepsilon)\mathrm{OPT}\) and no capacity violation ([Chau–Elbassioni–Khonji](https://arxiv.org/abs/1403.3907)).
A related fractional multiple-choice AC scheduling relaxation admits feasible additive-error approximation in time polynomial in input bit length and the logarithm of inverse error ([Combinatorial Optimization of AC Electric Power Systems](https://users.cecs.anu.edu.au/~sid.chau/FnT/FnT.pdf)).
The stated problem is exactly solvable in polynomial time, and hence admits a PTAS. The normalization \(\sum_t\mu_t=1\), together with \(\lVert d\rVert_2\le c\), makes the capacity constraint redundant.
I first prove this conclusion under the given premises. I then address a capacity-active variant, allowing individual demands to exceed \(c\), and prove that it also admits a feasible PTAS.
For any nonnegative allocation satisfying the type-mass equalities,
\(\displaystyle \sum_t\sum_{d\in D_t}x_{t,d}=\sum_t\mu_t=1.\)
The triangle inequality and the individual demand bounds therefore give
\(\displaystyle \left\lVert\sum_t\sum_{d\in D_t}x_{t,d}d\right\rVert_2 \le \sum_t\sum_{d\in D_t}x_{t,d}\lVert d\rVert_2 \le c\sum_t\sum_{d\in D_t}x_{t,d} =c. \)
Thus every allocation satisfying the type-mass equalities is feasible.
For each supported type, choose
\(\displaystyle d_t^\star\in\operatorname*{arg\,max}_{d\in D_t}v_t(d).\)
This maximum exists because the menu is finite and nonempty. Allocate \(x_{t,d_t^\star}=\mu_t\) and set every other coordinate to zero. The allocation is feasible by the preceding calculation.
For any feasible allocation \(x\), nonnegativity of its coordinates implies
\(\displaystyle \sum_{d\in D_t}x_{t,d}v_t(d) \le v_t(d_t^\star)\sum_{d\in D_t}x_{t,d} =\mu_t v_t(d_t^\star). \)
Summing over types proves
\(\displaystyle \mathrm{OPT}=\sum_t\mu_t v_t(d_t^\star), \)
and our allocation attains this value exactly. This argument includes the case \(\mathrm{OPT}=0\).
Scan each explicitly listed menu and compare rational valuations exactly. Comparing \(a/b\) with \(p/q\), where denominators are positive, amounts to comparing the integers \(aq\) and \(pb\). Since each input integer has at most \(L\) bits, schoolbook multiplication gives an \(O(L^2)\) bound per comparison.
There are at most \(m\) comparisons. Copying the selected masses into the output takes at most \(O(\tau L+m)\) time. Consequently, a conservative total bound is
\(\displaystyle O(mL^2+\tau L).\)
All output masses are input rationals or zero. The running time is independent of \(\varepsilon\) and \(\delta\), and no types outside the supplied support are enumerated. The angular and valuation-monotonicity assumptions are unnecessary for this exact solution.
To address the nontrivial capacity question, consider the variant obtained by dropping only the bounds \(\lVert d\rVert_2\le c\). Retain nonnegative demand coordinates, rational input, the mass constraints, and the zero option with zero valuation.
The following construction proves a feasible PTAS for this broader variant.
Fix \(0<\varepsilon<1\), and define
\(\displaystyle N=\lceil 1/\varepsilon\rceil,\qquad \alpha=1-\frac1N.\)
Then \(N\ge2\) and \(\alpha\ge1-\varepsilon\). For \(j=0,\ldots,N\), put
\(\displaystyle s_j=\frac jN,\qquad u_j=\left(\frac{1-s_j^2}{1+s_j^2},\frac{2s_j}{1+s_j^2}\right). \)
Each \(u_j\) is a rational unit vector in the first quadrant. Its angle is \(\theta_j=2\arctan(s_j)\). These angles increase from \(0\) to \(\pi/2\). Since the derivative of \(2\arctan(s)\) is at most \(2\), consecutive angles differ by at most \(2/N\). Every angle in the first quadrant is therefore within \(1/N\) of some \(\theta_j\).
Define the rational polyhedron
\(\displaystyle P=\{z\in\mathbb R_{\ge0}^2:u_j\cdot z\le\alpha c\text{ for }j=0,\ldots,N\}. \)
It has the two required containment properties:
\(\displaystyle \cos h\ge1-\frac1{2N^2}\ge1-\frac1N=\alpha. \)
Hence \(\alpha\lVert z\rVert_2\le u_j\cdot z\le\alpha c\). Since \(\alpha>0\), this proves \(\lVert z\rVert_2\le c\). The conclusion also holds for \(z=0\).
Thus \(P\) contains the quarter disk of radius \(\alpha c\) and lies within the quarter disk of radius \(c\).
Maximize the original welfare subject to the type-mass equalities, nonnegativity, and the rational linear inequalities
\(\displaystyle \sum_t\sum_{d\in D_t}x_{t,d}(u_j\cdot d)\le\alpha c, \qquad j=0,\ldots,N. \)
Every feasible solution of this linear program is feasible for the original capacity constraint, by the second containment property.
An optimum \(x^\star\) of the capacity-active problem exists: the product of the type simplices is compact, the capacity constraint defines a closed subset, and the all-zero-demand allocation establishes nonemptiness.
Construct an allocation \(y\) by setting
\(\displaystyle y_{t,d}=\alpha x^\star_{t,d}\quad(d\ne0), \qquad y_{t,0}=\alpha x^\star_{t,0}+(1-\alpha)\mu_t. \)
Its coordinates are nonnegative and sum to \(\mu_t\) for each type. Its aggregate demand is \(\alpha\) times that of \(x^\star\), so its norm is at most \(\alpha c\). The first containment property makes \(y\) feasible for the linear program. Because the zero option has zero valuation, its welfare is \(\alpha\mathrm{OPT}\).
An exact optimum of the rational linear program therefore has welfare at least
\(\displaystyle \alpha\mathrm{OPT}\ge(1-\varepsilon)\mathrm{OPT},\)
with no capacity violation.
The linear program has \(m\) variables, \(\tau\) mass equalities, and \(N+1\) additional inequalities. Each coefficient has \(O(L+\log N)\) bits. Its feasible region is nonempty and bounded, since the zero-demand allocation is feasible and \(0\le x_{t,d}\le\mu_t\).
The polynomial-time solvability theorem for rational linear programming therefore applies and returns an exact rational optimum in time
\(\displaystyle \operatorname{poly}(m,\tau,L,1/\varepsilon).\)
This establishes a PTAS even for the capacity-active variant. For the task as stated, the stronger exact algorithm in Section 1 settles the question.
⟨structured verdict parsed — rendered above⟩
The prover’s answer correctly resolves the stated problem: it gives an exact polynomial-time algorithm. The additional capacity-active variant is also supported by a valid approximation argument. No mathematical errors or substantive gaps were found.
The prover uses the explicit assumptions that the total population mass is \(1\) and every individual demand has norm at most \(c\). These are stated premises, so exploiting their joint consequence is legitimate; this is not an unintended degenerate interpretation.
The exact algorithm considers only the supplied support and explicitly listed menus, as required.
Summing the type-mass equalities gives
\[
\sum_t\sum_{d\in D_t}x_{t,d}=1.
\]
The triangle inequality applies to the finite sum. Because each allocation coordinate is nonnegative,
\[
\lVert x_{t,d}d\rVert_2=x_{t,d}\lVert d\rVert_2.
\]
Every demand, including \(0\), has norm at most \(c\). Consequently, the displayed upper bound by \(c\) is valid.
Thus every allocation satisfying nonnegativity and the type-mass equalities satisfies capacity. This is the decisive step, and it is correct.
Each menu is finite and contains \(0\), so a valuation maximizer exists. Assigning the entire mass of each type to one selected maximizer satisfies its mass equality and nonnegativity. Capacity feasibility follows from the preceding argument.
For any allocation, every valuation in type \(t\)’s menu is bounded above by \(v_t(d_t^\star)\). Multiplication by nonnegative allocation masses and summation therefore establish the claimed typewise welfare bound. Summing these bounds establishes
\[
\mathrm{OPT}=\sum_t\mu_t v_t(d_t^\star).
\]
Ties cause no difficulty. The argument also covers singleton menus and \(\mathrm{OPT}=0\). Neither the angular restriction nor valuation monotonicity is needed.
The rational-comparison calculation is correct when denominators are positive, as they can be taken in the input representation. Each cross-product involves integers with at most \(L\) bits, so schoolbook multiplication costs \(O(L^2)\).
At most \(m\) comparisons suffice to select all menu maximizers. Output coordinates are copied input masses or zeros, so their representation requires no new high-precision arithmetic. The conservative bound
\[
O(mL^2+\tau L)
\]
is valid and includes the stated output cost, since \(mL^2\) absorbs \(m\).
The algorithm is independent of \(\varepsilon\), and exact optimality implies the requested approximation guarantee for every permitted \(\varepsilon\).
This section goes beyond the assignment but is mathematically consistent.
The choices \(N=\lceil1/\varepsilon\rceil\) and \(\alpha=1-1/N\) satisfy \(N\ge2\), \(\alpha>0\), and \(\alpha\ge1-\varepsilon\).
The parametrized vectors are rational unit vectors: their squared-norm numerator is
\[
(1-s_j^2)^2+4s_j^2=(1+s_j^2)^2.
\]
Their angles cover the first quadrant in increasing order. The derivative bound gives consecutive angular gaps at most \(2/N\), which implies the claimed nearest-vector distance at most \(1/N\), including endpoint intervals.
Both containment arguments are valid:
The existence argument checks compactness, closedness, and nonemptiness correctly.
The constructed allocation \(y\) preserves every type’s total mass and remains nonnegative. Its aggregate demand and welfare scale by \(\alpha\), using the zero demand’s zero valuation. The first containment property therefore supplies the required feasible comparison allocation for the linear program. An exact linear-program optimum attains at least its welfare and is capacity-feasible by the second containment property.
The rational linear-programming theorem is applied within its stated setting: finitely many explicitly represented rational constraints, a nonempty bounded feasible region, and a rational linear objective. The coefficient-length bound \(O(L+\log N)\) is valid. Thus the asserted polynomial dependence on \(m,\tau,L,1/\varepsilon\) follows.
No repair or additional clarification is needed to verify the target conclusion.
⟨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.