Answer: \(\mathrm{NP}\)-hard to approximate within \(k^{1-\varepsilon}\) for every fixed \(0<\varepsilon<1\).
Theorem 4.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe Ad Types problem with Gap Rules hard to approximate better than k1−ǫ for any ǫ > 0, unless P = NP, even when the discount curves of all the ad types are identically equal to 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given categories \(\Theta\), a finite support \(\mathcal T\) of complete advertiser types \(t=(\theta,v)\) with rational masses \(\mu_t\) summing to \(1\), and \(N\) ordered slots with rational capacities \(q_j\) summing to \(1\), nonincreasing discounts \(\alpha_{\theta,j}\), and gap matrix \(G\), choose \(z_{t,j}\in\{0,1\}\) and assigned masses \(x_{t,j}\ge 0\). Require \(\sum_t z_{t,j}\le 1\), \(x_{t,j}\le q_jz_{t,j}\), and \(\sum_jx_{t,j}\le\mu_t\); if \(z_{t,j}=1\) for category \(\theta\), then \(z_{t',\ell}=0\) for every type \(t'\) of category \(\phi\) and every \(1\le\ell-j\le G_{\theta\phi}\). Maximize \(\sum_{t=(\theta,v),j}v\alpha_{\theta,j}x_{t,j}\).
Let \(\Theta\) be a nonempty set of \(k\) categories. A society is given by its support: a list \(\mathcal T\) of \(\tau\) distinct complete types \(t=(\theta,v)\), each with positive binary rational mass \(\mu_t\), where \(v\ge0\) is rational and \(\sum_t\mu_t=1\). Every category occurs in the support; \(\tau\) counts listed types, not all possible types.
There are \(m=N\ge1\) ordered slots with positive rational capacities \(q_j\) satisfying \(\sum_jq_j=1\). Each category has rational discounts \(\alpha_{\theta,1}\ge\cdots\ge\alpha_{\theta,m}\ge0\). The directed gap matrix has entries \(G_{\theta\phi}\in\mathbb Z_{\ge0}\), including diagonal entries.
Choose \(z_{t,j}\in\{0,1\}\) and real masses \(x_{t,j}\ge0\), subject to \(\sum_tz_{t,j}\le1\), \(x_{t,j}\le q_jz_{t,j}\), and \(\sum_jx_{t,j}\le\mu_t\). Mass may be split across slots; capacities and supply may remain unused.
For all \(t=(\theta,v)\), \(t'=(\phi,v')\), and slots \(j<\ell\) with \(\ell-j\le G_{\theta\phi}\), require \(z_{t,j}+z_{t',\ell}\le1\). Gaps count slot indices, irrespective of capacities or intervening empty slots.
Maximize \(W=\sum_{t=(\theta,v),j}v\alpha_{\theta,j}x_{t,j}\), and let \(\mathrm{OPT}\) denote its maximum. Let \(L\) be the total binary input length; express running times in \(m,\tau,k,L\).
For each fixed \(0<\varepsilon<1\), is there an algorithm polynomial in \(m,\tau,k,L\) that returns a feasible allocation with \(W\ge\mathrm{OPT}/k^{1-\varepsilon}\), or is achieving this approximation guarantee NP-hard?
The discrete problem assigns each individual ad to at most one slot and is NP-hard to approximate within \(k^{1-\varepsilon}\) for every fixed \(0<\varepsilon<1\), even with all discounts equal to \(1\); it also has an exact \(O(km^{2k+1})\) dynamic program ([verified discrete results](https://arxiv.org/pdf/1907.04400)).
No result settling this exact mass allocation model was located in the literature search.
For every fixed \(0<\varepsilon<1\), achieving the guarantee \(W\ge \mathrm{OPT}/k^{1-\varepsilon}\) is \(\mathrm{NP}\)-hard. Thus no algorithm polynomial in \(m,\tau,k,L\) achieves this guarantee unless \(\mathrm{P}=\mathrm{NP}\).
The hardness holds with all discounts equal to \(1\), symmetric gaps, zero diagonal gaps, and dyadic masses and capacities. The proof explicitly allows mass splitting.
For every fixed \(0<\varepsilon<1\), approximating maximum independent set on an \(n\)-vertex graph within \(n^{1-\varepsilon}\) is \(\mathrm{NP}\)-hard. This follows from [Zuckerman’s maximum-clique hardness theorem](https://www.theoryofcomputing.org/articles/v003a006/) by taking graph complements: complementation preserves the number of vertices and converts cliques into independent sets of exactly the same cardinality.
We give an approximation-preserving reduction from this problem.
Let \(H=(V,E)\) be a simple undirected graph with \(n\ge1\) vertices. Write \(a(H)\) for its maximum independent-set cardinality.
Set \(k=n\), with one category \(\theta_u\) for each vertex \(u\in V\). Let \(b\) be the smallest power of two satisfying \(b\ge n\). Set \(m=N=b\).
Construct the support as follows:
The additional type introduces no additional category. Consequently, \(\tau=k\) when \(b=n\), and \(\tau=k+1\) otherwise. All listed types are distinct, all listed masses are positive, every category occurs, and the masses sum to \(1\). All masses are dyadic.
For every slot \(j\), set \(q_j=1/b\). For every category and slot, set \(\alpha_{\theta,j}=1\). These capacities are positive and sum to \(1\), and the discounts satisfy the required monotonicity.
Finally, define
\(\displaystyle G_{\theta_u\theta_v}=\begin{cases}b,&\{u,v\}\in E,\\0,&\text{otherwise}.\end{cases}\)
The matrix is symmetric and has zero diagonal. For adjacent vertices, the gap covers every possible distance between two slots, because that distance is at most \(b-1\).
We prove that \(\mathrm{OPT}=a(H)/b\).
Given a feasible allocation \((z,x)\), define
\(\displaystyle S=\{u\in V:\text{some listed type of category }\theta_u\text{ has }z_{t,j}=1\text{ for some }j\}.\)
Suppose adjacent vertices \(u,v\) both belonged to \(S\). Choose witnessing assignments in slots \(j,\ell\).
They cannot occupy the same slot, because each slot permits at most one selected type. If \(j<\ell\), then \(\ell-j\le b-1\le G_{\theta_u\theta_v}\), so the gap constraint forbids the two assignments. If \(\ell<j\), the symmetric gap gives the same contradiction. Therefore \(S\) is independent.
The only positive-valued type in category \(\theta_u\) is \(t_u\), whose total supply is \(1/b\). The additional type, if present, contributes zero welfare. Since all discounts equal \(1\), every feasible allocation satisfies
\(\displaystyle W=\sum_{u\in V}\sum_{j=1}^{b}x_{t_u,j}\le\sum_{u\in S}\mu_{t_u}=\frac{|S|}{b}\le\frac{a(H)}{b}.\)
This inequality uses the total supply constraint for each type, so it remains valid when its mass is split across multiple slots.
Let \(I\subseteq V\) be independent. Assign each type \(t_u\), for \(u\in I\), to a different slot, and place mass \(1/b\) there. Set all other variables to zero.
There are enough slots because \(|I|\le n\le b\). Each occupied slot receives exactly its capacity, and each selected type uses exactly its supply.
Each selected category occurs once, so diagonal gaps cause no restriction. Distinct selected categories correspond to nonadjacent vertices, so their gaps are zero; their distinct slot indices have positive distance and hence trigger no gap constraint.
The allocation is therefore feasible and has welfare \(|I|/b\). Taking a maximum independent set proves \(\mathrm{OPT}\ge a(H)/b\), completing the equality.
Suppose an algorithm polynomial in \(m,\tau,k,L\) returned a feasible allocation satisfying \(W\ge\mathrm{OPT}/k^{1-\varepsilon}\). Apply it to the constructed instance and extract \(S\) from its binary assignment variables.
The preceding proof gives
\(\displaystyle |S|\ge bW\ge\frac{b\,\mathrm{OPT}}{k^{1-\varepsilon}}=\frac{a(H)}{n^{1-\varepsilon}}.\)
Thus the algorithm would approximate maximum independent set within \(n^{1-\varepsilon}\).
The reduction has \(k=n\), \(m=b<2k\), and \(\tau\le k+1\). Its binary input length is \(L=O(k^2\log(k+1))\), and it can be constructed within that many bit operations. Extracting \(S\) requires \(O(m\tau)\) inspections of binary assignment variables. Hence a running time polynomial in \(m,\tau,k,L\) would give a polynomial-time algorithm for the prohibited independent-set approximation.
This proves the claimed hardness for the exact mass-allocation model.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned question. The reduction establishes that, for every fixed \(0<\varepsilon<1\), achieving \(W\ge\mathrm{OPT}/k^{1-\varepsilon}\) is NP-hard. No major or minor mathematical issues were found.
The argument accounts for mass splitting, unused capacity, unused supply, and binary selections carrying zero mass.
Zuckerman’s Theorem 1.1 states that, for every fixed \(\varepsilon>0\), approximating maximum clique within \(n^{1-\varepsilon}\) is NP-hard. This is the required deterministic hardness theorem, supporting the stated consequence unless \(\mathrm{P}=\mathrm{NP}\). [Original theorem, page 104](https://www.theoryofcomputing.org/articles/v003a006/v003a006.pdf).
The prover correctly transfers this theorem to maximum independent set by graph complementation. Complementation preserves the vertex count and identifies cliques with independent sets of equal cardinality. Consequently, both the optimum and the approximation factor are preserved. The task’s range \(0<\varepsilon<1\) lies within the theorem’s range.
For \(n\ge1\), the smallest power of two \(b\ge n\) satisfies \(n\le b<2n\). Thus \(k=n\) and \(m=b\) are positive.
The support is valid:
The capacities \(q_j=1/b\) are positive and sum to \(1\). Constant discounts equal to \(1\) satisfy all monotonicity and nonnegativity requirements.
Because \(H\) is simple and undirected, the specified gap matrix has nonnegative integer entries, is symmetric, and has zero diagonal. For an edge, its gap \(b\) covers every possible positive slot distance, which is at most \(b-1\). The model imposes no upper bound violated by choosing this gap.
The definition of \(S\) includes every category with a selected binary assignment, regardless of its assigned mass. This is consistent with the model, whose gap restrictions apply to \(z\).
If adjacent vertices \(u,v\) both lie in \(S\), their witnessing assignments cannot occupy the same slot because the corresponding types are distinct and the slot permits at most one selection.
If their slots differ, whichever assignment occurs earlier triggers the applicable gap constraint: symmetry supplies the required directed entry in either ordering, and the distance is at most \(b-1\). Both selections therefore cannot equal \(1\).
Thus \(S\) is independent. This reasoning also covers selections of the additional zero-valued type.
All positive-valued types have value \(1\), all discounts equal \(1\), and the optional additional type contributes zero welfare. Therefore the displayed expression for \(W\) is correct.
The capacity-linking constraint implies that positive mass requires a selected assignment. Hence every positive-valued type contributing welfare belongs to a category in \(S\).
For each such type, the total supply constraint bounds its mass across all slots by \(1/b\). Summing these bounds gives precisely the prover’s inequality \(W\le |S|/b\le a(H)/b\). Splitting mass cannot evade this bound.
There are enough distinct slots because \(|I|\le n\le b\). Each selected type receives mass equal to both its supply and its slot’s capacity. All other variables are zero.
The selected categories occur once each, and distinct selected categories are nonadjacent. Their gaps are zero, so no pair of distinct occupied slots triggers a gap restriction.
The constructed allocation is feasible and has welfare \(|I|/b\). Together with the preceding upper bound, this establishes \(\mathrm{OPT}=a(H)/b\).
The extraction uses the returned binary assignments, so it does not require numerical comparisons involving real masses.
The inequality \(|S|\ge bW\), the assumed welfare guarantee, the optimal-value identity, and \(k=n\) yield exactly the displayed bound \(|S|\ge a(H)/n^{1-\varepsilon}\).
There is no loss in the approximation exponent: rounding the slot count to \(b\) does not increase the category count \(k\).
The stated bounds \(m<2k\) and \(\tau\le k+1\) hold, including when \(n=1\).
The explicit gap matrix has \(k^2\) entries, each requiring \(O(\log(k+1))\) bits. The remaining support, capacities, and discount data fit within the claimed total bound \(L=O(k^2\log(k+1))\). Construction within this bit-operation bound is consistent with an explicit graph representation.
Extracting \(S\) requires \(O(m\tau)\) binary-variable inspections. Thus polynomial running time in \(m,\tau,k,L\) would give polynomial running time for the forbidden independent-set approximation.
None. The proof settles the exact mass-allocation model under the usual polynomial-time interpretation of the question.
⟨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.