Answer: Exactly solvable in deterministic time polynomial in \(m,\tau,L\); therefore the requested \(m^{1/2-\varepsilon}\)-approximation exists for every fixed \(0<\varepsilon<\tfrac12\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateUnless NP=ZPP1, the WMSP problem can- not be approximated within n1/2−ǫ in polynomial time, for any ǫ > 0.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(n\) commodities, bid types \(t=1,\ldots,\tau\) with rational masses \(\mu_t\) summing to \(1\), bundle vectors \(q(t)\), prices \(p_t\), and rational per-capita supplies \(\kappa_j\), choose accepted masses \(x_t\) satisfying \(0\le x_t\le\mu_t\) and \(\sum_t q_j(t)x_t\le\kappa_j\) for each commodity \(j\), to maximize \(\sum_t p_t x_t\).
There are \(m\ge 2\) commodities. A society is given by its support: the list of \(\tau\ge 1\) bid types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Type \(t\) requests a bundle \(q(t)\in\mathbb Z_{\ge 0}^m\) and offers a nonnegative binary rational price \(p_t\) for that entire bundle. Per-capita supplies \(\kappa_j\) are positive binary rationals. Bundle coordinates need not be bounded by per-capita supplies.
An allocation chooses real accepted masses \(x_t\) satisfying \(0\le x_t\le\mu_t\) and \(\sum_t q_j(t)x_t\le\kappa_j\) for every commodity. These are the only feasibility constraints; there are no mutually exclusive bids.
Its revenue is \(V(x)=\sum_t p_tx_t\), and \(\mathrm{OPT}\) is the maximum feasible revenue. Let \(L\) be the total binary input length.
For each fixed \(0<\varepsilon<\tfrac12\), is there an algorithm polynomial in \(m,\tau,L\) that returns a feasible allocation with revenue at least \(\mathrm{OPT}/m^{1/2-\varepsilon}\), or is achieving this approximation impossible unless \(\mathrm{NP}=\mathrm{ZPP}\)?
For discrete weighted multi-set packing, polynomial-time approximation within \(m^{1/2-\varepsilon}\) is impossible unless \(\mathrm{NP}=\mathrm{ZPP}\), for every fixed \(\varepsilon>0\). [Source](https://arxiv.org/pdf/cs/0202032).
No separate approximation theorem for the distribution-over-types formulation was verified.
The stated problem is exactly solvable in deterministic polynomial time. Consequently, the requested approximation exists for every fixed \(0<\varepsilon<\tfrac12\), without any complexity assumption.
The decisive premise is that accepted masses \(x_t\) may be real numbers. Under the given feasibility constraints, the problem is a rational linear program.
Define \(Q\in\mathbb Z_{\ge 0}^{m\times\tau}\) by \(Q_{jt}=q_j(t)\), and let \(p\), \(\mu\), and \(\kappa\) be the corresponding input vectors. Consider the linear program
\(\displaystyle \text{maximize }p^\mathsf T x\quad\text{subject to }Qx\le\kappa,\quad 0\le x\le\mu.\)
Its variables are precisely the accepted masses. Its inequalities are precisely the feasibility constraints in the question, and its objective is precisely the revenue. Thus its optimal value equals \(\mathrm{OPT}\); no relaxation or rounding is involved.
The feasible region is nonempty because \(x=0\) is feasible. It is closed and contained in the bounded box \(\prod_{t=1}^{\tau}[0,\mu_t]\), hence compact. The continuous linear objective therefore attains its maximum. Moreover, nonnegativity of the prices gives the finite bound
\(\displaystyle 0\le\mathrm{OPT}\le\sum_{t=1}^{\tau}p_t\mu_t.\)
We use the standard polynomial-time theorem for rational linear programming: an explicitly represented linear program with rational coefficients can be solved in time polynomial in its binary encoding length; when its feasible region is nonempty and its optimum is finite, an exact rational optimal solution can be returned. This is the classical consequence of the ellipsoid method. See [Khachiyan, *Polynomial algorithms in linear programming*](https://www.mathnet.ru/php/archive.phtml?jrnid=zvmmf&option_lang=eng&paperid=5239&wshow=paper).
All hypotheses hold here:
Large bundle coordinates cause no difficulty: the algorithm uses their binary representations and never expands a coordinate into individual units.
For completeness, an exact optimal allocation also has polynomial binary output length. Let \(D\) be the product of the denominators of all input rationals. Then \(\log_2D\le L\). Multiplying the constraints by \(D\) gives integer coefficients whose absolute values are at most \(H=2^{2L}\).
A nonempty compact polytope has an optimal vertex. At a vertex, \(\tau\) linearly independent active constraints determine the coordinates. By Cramer's rule, each coordinate is a ratio of determinants of integer matrices of order \(\tau\). The determinant expansion bounds the absolute values of these determinants by \(\tau!H^\tau\). Hence each coordinate has binary encoding length \(O(\tau(L+\log\tau))\). This confirms that an exact rational allocation can be represented with polynomially many bits.
The algorithm is therefore simply to construct this linear program, solve it exactly, and return its optimal solution \(x^*\).
Since \(m\ge2\), \(1/2-\varepsilon>0\), and \(\mathrm{OPT}\ge0\),
\(\displaystyle V(x^*)=\mathrm{OPT}\ge\frac{\mathrm{OPT}}{m^{1/2-\varepsilon}}.\)
Discrete packing requires choosing whole bids. That restriction is absent here. Indeed, setting \(y_t=x_t/\mu_t\) transforms the given problem into
\(\displaystyle \text{maximize }\sum_t p_t\mu_t y_t,\quad \text{subject to }\sum_t q_j(t)\mu_t y_t\le\kappa_j,\quad 0\le y_t\le1.\)
Requiring \(y_t\in\{0,1\}\) would introduce a different problem. The supplied paper explicitly distinguishes binary bid selection from its linear programming relaxation in Section 3.1. [Gonen and Lehmann, *Optimal Solutions for Multi-Unit Combinatorial Auctions*](https://arxiv.org/pdf/cs/0202032).
The distinction can affect the optimum even in a small instance. Take \(m=\tau=3\), masses \(\mu_t=1/3\), supplies \(\kappa_j=1/3\), prices \(p_t=3\), and bundles
\(\displaystyle q(1)=(1,1,0),\quad q(2)=(1,0,1),\quad q(3)=(0,1,1).\)
Accepting each type at mass \(x_t=1/6\) uses exactly \(1/3\) of each commodity and earns revenue \(3/2\). Summing the three supply constraints gives \(2(x_1+x_2+x_3)\le1\), so this revenue is optimal.
If each type instead had to be accepted wholly or rejected, any two accepted types would exceed their shared commodity's supply. The optimal revenue under that additional restriction would be \(1\).
Thus the discrete hardness theorem does not settle the stated continuous problem. The exact linear programming algorithm does.
⟨structured verdict parsed — rendered above⟩
Result: proved. The prover correctly resolves the stated continuous problem by exact rational linear programming. No major or minor mathematical issues were found.
The formulation
\[
\max p^{\mathsf T}x
\quad\text{subject to}\quad
Qx\le\kappa,\qquad 0\le x\le\mu
\]
matches the task exactly:
There are no additional feasibility requirements to encode. In particular, the prover does not impose integrality or mutually exclusive bids. The assertion that this LP has optimal value \(\mathrm{OPT}\) is correct.
The zero vector satisfies every constraint. The feasible set is closed and lies in the bounded box \(\prod_t[0,\mu_t]\), so it is compact. The linear objective is continuous and therefore attains its maximum.
The bound
\[
0\le\mathrm{OPT}\le\sum_t p_t\mu_t
\]
follows from nonnegative prices and the coordinate bounds. It also handles zero prices and \(\mathrm{OPT}=0\).
The prover states the applicable standard theorem adequately: explicitly represented rational LPs admit deterministic algorithms polynomial in binary encoding length, and a feasible LP with finite optimum admits exact rational optimal output.
The hypothesis checks are correct. This instance has \(\tau\) variables and \(m+2\tau\) inequalities, all with rational coefficients. Its explicit matrix has polynomial encoding length in \(m,\tau,L\). Feasibility and finiteness have already been established.
The reference to the classical ellipsoid-method result is appropriate; the linked bibliographic entry identifies Khachiyan’s cited paper. [Khachiyan, *Polynomial algorithms in linear programming*](https://www.mathnet.ru/php/archive.phtml?jrnid=zvmmf&option_lang=eng&paperid=5239&wshow=paper).
Unbounded bundle coordinates do not invalidate this application: their binary lengths, rather than their numerical magnitudes, enter the complexity bound.
The supplementary determinant argument is correct.
The product \(D\) of input denominators satisfies \(\log_2D\le L\). After scaling the constraints, every matrix and right-hand-side entry is an integer of absolute value at most \(H=2^{2L}\).
A nonempty compact polytope has an optimal vertex. At a vertex, \(\tau\) independent active constraints determine the coordinates, including in degenerate cases. Cramer’s rule applies because the selected coefficient matrix is nonsingular.
Both its determinant and the determinants obtained by replacing a column with the right-hand side satisfy
\[
|\det|\le\tau!H^\tau.
\]
Thus each coordinate has binary encoding length \(O(\tau(L+\log\tau))\), as claimed. The entire allocation consequently has polynomial output length.
For the assigned range of \(\varepsilon\) and \(m\), the denominator \(m^{1/2-\varepsilon}\) exceeds one. Since \(\mathrm{OPT}\ge0\), the exact optimal allocation satisfies the requested inequality. The algorithm works uniformly and does not require computing that denominator.
The substitution \(y_t=x_t/\mu_t\) is valid because every mass is positive. The transformed constraints and objective are correct. Imposing binary \(y_t\) would change the assigned problem.
The source attribution is accurate: Section 3.1 explicitly distinguishes binary bid selection from its continuous LP relaxation. [Gonen and Lehmann, Section 3.1](https://arxiv.org/pdf/cs/0202032).
The example also checks out. Each commodity receives mass \(1/3\), and the revenue is \(3/2\). Summing the constraints yields the asserted upper bound. Under whole-type acceptance, every pair violates a shared supply constraint, while one accepted type earns \(1\).
Repair feedback: None 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.