Answer: Yes. A randomized algorithm running in polynomial time in \(m,\tau,L\) always returns a feasible allocation \(\nu\) with \(\mathbb{E}[W(\nu)]\geq\mathrm{OPT}/(16\rho_H)\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm~\ref{algo:MultiUnit} returns a feasible allocation of social welfare at least $\nicefrac{b^\ast}{16 \rho}$ in expectation.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), an unweighted conflict graph \(H\) on \(T\), \(k\) channels, and symmetric valuation curves \(b_t(i)\), find a feasible mass allocation \(\nu_{t,S}\geq 0\) with \(\sum_{S\subseteq[k]}\nu_{t,S}=\mu_t\). For each channel \(j\), the types with \(\sum_{S\ni j}\nu_{t,S}>0\) must form an independent set of \(H\). Is there a randomized algorithm polynomial in \(\tau=|T|\), \(k\), and the input bit length that returns such an allocation with expected welfare \(\sum_{t\in T}\sum_{S\subseteq[k]}\nu_{t,S}b_t(|S|)\geq \mathrm{OPT}/(16\rho_H)\), where \(\rho_H\) is the inductive independence number of \(H\)?
A society is given by its support: the list of \(\tau=|T|\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=k\geq1\) channels and a simple undirected conflict graph \(H\) on \(T\). Each symmetric valuation is explicitly tabulated as \(b_t:\{0,\ldots,k\}\to\mathbb{Q}_{\geq0}\), with \(b_t(0)=0\); monotonicity is not required. Let \(L\) be the total input bit length.
Write \(N_H(t)\) for the neighbors of \(t\). Using symmetrized unit edge weights, define \(\rho_H=\max\{1,\min_\pi\max_{t,\,I\text{ independent in }H}2|I\cap N_H(t)\cap\{u:\pi(u)<\pi(t)\}|\}\). An ordering attaining this bound and \(\rho_H\) are supplied as promised input.
An allocation consists of masses \(\nu_{t,S}\geq0\), for \(S\subseteq[k]\), satisfying \(\sum_S\nu_{t,S}=\mu_t\). For every channel \(j\), the set \(\{t:\sum_{S\ni j}\nu_{t,S}>0\}\) must be independent in \(H\); portions of the same type do not conflict with one another.
Define \(W(\nu)=\sum_t\sum_{S\subseteq[k]}\nu_{t,S}b_t(|S|)\) and \(\mathrm{OPT}=\max_{\nu\text{ feasible}}W(\nu)\). Represent an output by its nonzero binary rational entries, with omitted entries zero.
Does a randomized algorithm running in \(\operatorname{poly}(m,\tau,L)\) time always return a feasible allocation \(\nu\) with \(\mathbb{E}[W(\nu)]\geq\mathrm{OPT}/(16\rho_H)\)?
For discrete users with symmetric valuations and a supplied witnessing ordering, a polynomial-time randomized algorithm achieves expected welfare at least \(\mathrm{OPT}_{\mathrm{disc}}/(16\rho)\). [Verified source](https://arxiv.org/pdf/1110.5753).
No result settling this precise mass-allocation approximation question was located in the literature search.
Yes. There is a randomized algorithm with worst-case running time polynomial in \(m,\tau,L\) that always outputs a feasible allocation and satisfies the requested expectation bound.
The essential observation is that splitting a type’s mass cannot improve the optimum. Below, I prove this and give an explicit rounding algorithm, including finite-bit sampling. The construction uses the cardinality relaxation and two-range rounding approach underlying the supplied [discrete approximation theorem](https://arxiv.org/pdf/1110.5753).
Define a discrete instance with one user for each \(t\in T\), conflict graph \(H\), and valuation
\(c_t(i)=\mu_t b_t(i)\) for \(i\in\{0,\ldots,k\}\).
A discrete allocation specifies a bundle \(S_t\subseteq[k]\) for every type. It is feasible when \(\{t:j\in S_t\}\) is independent for every channel \(j\). Its welfare is
\(C(S)=\sum_t c_t(|S_t|)\).
Write \(D\) for the maximum discrete welfare.
Every feasible discrete allocation gives a feasible mass allocation by setting \(\nu_{t,S_t}=\mu_t\) and all other entries to zero. Consequently, \(\mathrm{OPT}\geq D\).
Conversely, let \(\nu\) be any feasible mass allocation. Since \(\mu_t>0\), the finite family
\(\mathcal A_t=\{S\subseteq[k]:\nu_{t,S}>0\}\)
is nonempty. Choose \(S_t\in\mathcal A_t\) maximizing \(b_t(|S_t|)\).
For each channel \(j\),
\(\{t:j\in S_t\}\subseteq\{t:\sum_{S\ni j}\nu_{t,S}>0\}\).
The latter set is independent by feasibility of \(\nu\), and every subset of an independent set is independent. Thus the selected discrete allocation is feasible.
Furthermore, for each type,
\(\sum_S\nu_{t,S}b_t(|S|)\leq\sum_S\nu_{t,S}b_t(|S_t|)=\mu_t b_t(|S_t|)\).
Summing gives \(W(\nu)\leq C(S)\leq D\). Hence
\(\mathrm{OPT}=D\).
This argument does not require monotonicity. It also proves that the mass optimum is attained by an allocation with exactly one nonzero entry per type.
Put \(\rho=\rho_H\), and let \(\pi\) be the supplied witnessing ordering. Define
\(P_t=\{u\in N_H(t):\pi(u)<\pi(t)\}\).
The promise implies that, for every independent set \(I\),
\(2|I\cap P_t|\leq\rho\).
Consider the following rational linear program, with variables \(x_{t,i}\) for \(t\in T\) and \(i\in\{1,\ldots,k\}\):
\(\displaystyle B=\max\sum_{t\in T}\sum_{i=1}^k c_t(i)x_{t,i}\),
subject to
\(\displaystyle 2\sum_{u\in P_t}\sum_{i=1}^k i\,x_{u,i}\leq\rho k\quad\text{for every }t\in T,\)
\(\displaystyle \sum_{i=1}^k x_{t,i}\leq1\quad\text{for every }t\in T,\qquad x_{t,i}\geq0.\)
To verify that \(B\geq D\), take any feasible discrete allocation and set \(x_{t,i}=1\) when \(|S_t|=i>0\), with all other variables zero. For \(I_j=\{u:j\in S_u\}\), feasibility makes \(I_j\) independent. Therefore
\(\displaystyle 2\sum_{u\in P_t}|S_u|=\sum_{j=1}^k2|I_j\cap P_t|\leq\rho k.\)
Thus this integral vector satisfies every LP constraint and has the same welfare as the discrete allocation. In particular,
\(B\geq D=\mathrm{OPT}\).
The LP has \(k\tau\) variables and polynomially many explicitly represented constraints. Its coefficients have polynomial bit length: in particular, multiplying the input rationals \(\mu_t\) and \(b_t(i)\) increases their encoding lengths by at most their combined lengths, up to a constant.
The standard polynomial-time theorem for rational linear programming therefore yields an exact optimal rational solution \(x\) of polynomial encoding length. Its hypotheses hold here: the zero vector is feasible, and the constraints imply \(0\leq x_{t,i}\leq1\), so the feasible region is bounded.
If \(B=0\), return the allocation giving every type the empty bundle. Since \(B\geq\mathrm{OPT}\geq0\), this already satisfies the guarantee.
Otherwise, let \(a\) be the smallest positive coordinate of \(x\). Choose an integer \(q\geq0\) such that \(2^{-q}\leq a/(4\rho)\), and define
\(\displaystyle p_{t,i}=2^{-q}\left\lfloor\frac{2^q x_{t,i}}{2\rho}\right\rfloor.\)
For every coordinate,
\(\displaystyle \frac{x_{t,i}}{4\rho}\leq p_{t,i}\leq\frac{x_{t,i}}{2\rho}.\)
Indeed, the upper bound follows from rounding down. For a positive coordinate, the rounding error is at most \(2^{-q}\leq a/(4\rho)\leq x_{t,i}/(4\rho)\), proving the lower bound. Both bounds also hold for zero coordinates.
Partition the positive cardinalities into
\(A_1=\{i:1\leq i\leq k/2\}\) and
\(A_2=\{i:k/2<i\leq k\}\).
Run the following procedure separately for each \(\ell\in\{1,2\}\):
These probability distributions are valid because
\(\sum_{i\in A_\ell}p_{t,i}\leq(2\rho)^{-1}\sum_i x_{t,i}\leq1/2\).
Every resulting allocation is feasible: whenever a type receives a channel, no earlier neighbor has that channel. Thus no edge has both endpoints assigned the same channel.
Fix one round, a type \(t\), and a positive requested cardinality \(i\in A_\ell\). The requests of types preceding \(t\) are independent of \(D_t\). Also,
\(\displaystyle \mathbb E\!\left[\sum_{u\in P_t}D_u\right]=\sum_{u\in P_t}\sum_{h\in A_\ell}h\,p_{u,h}\leq\frac1{2\rho}\sum_{u\in P_t}\sum_{h=1}^k h\,x_{u,h}\leq\frac{k}{4}.\)
Suppose \(\ell=1\), so \(i\leq k/2\). If \(t\) fails to receive \(i\) channels, more than \(k-i\) channels are blocked by earlier neighbors. Their number is at most \(\sum_{u\in P_t}D_u\). Failure therefore implies
\(\sum_{u\in P_t}D_u>k/2\).
By Markov’s inequality and independence from \(D_t\),
\(\displaystyle \Pr(t\text{ fails}\mid D_t=i)\leq\frac{k/4}{k/2}=\frac12.\)
Suppose \(\ell=2\). Failure requires at least one earlier neighbor with a positive request: if all earlier neighboring requests are zero, every channel is available.
Because every positive request in this round exceeds \(k/2\),
\(\displaystyle \sum_{u\in P_t}\Pr(D_u>0)=\sum_{u\in P_t}\sum_{h\in A_2}p_{u,h}\leq\frac2k\sum_{u\in P_t}\sum_{h\in A_2}h\,p_{u,h}\leq\frac12.\)
The union bound, again using independence from \(D_t\), gives
\(\Pr(t\text{ fails}\mid D_t=i)\leq1/2\).
Thus, in either round,
\(\displaystyle \Pr(|S_t^{(\ell)}|=i)\geq\frac12p_{t,i}\geq\frac{x_{t,i}}{8\rho}.\)
Since every \(c_t(i)\) is nonnegative and \(c_t(0)=0\), it follows that
\(\displaystyle \mathbb E[C(S^{(\ell)})]\geq\frac1{8\rho}\sum_t\sum_{i\in A_\ell}c_t(i)x_{t,i}.\)
Return whichever of the two allocations has greater welfare. Pointwise, its welfare is at least their average. Consequently,
\(\displaystyle \mathbb E[C(S)]\geq\frac12\bigl(\mathbb E[C(S^{(1)})]+\mathbb E[C(S^{(2)})]\bigr)\geq\frac{B}{16\rho}\geq\frac{\mathrm{OPT}}{16\rho_H}.\)
For \(k=1\), the first range is empty; all arguments remain valid.
Because \(x\) has polynomial encoding length, the smallest positive coordinate \(a\) has polynomially many bits. Hence \(q\) can be chosen polynomially bounded and computed using exact integer arithmetic.
Each request distribution has probabilities that are integer multiples of \(2^{-q}\). Sampling uses exactly \(q\) independent fair bits to select a uniform integer in \(\{0,\ldots,2^q-1\}\), followed by comparison with cumulative integer probabilities. This gives a worst-case polynomial running time without rejection sampling.
The two greedy rounds and the exact welfare comparison also take polynomial time. Finally, output \(\nu_{t,S_t}=\mu_t\) for every type, omitting all other entries. There are exactly \(\tau\) entries; each bundle uses a \(k\)-bit mask, and each mass retains its input representation. Every random outcome therefore produces a feasible, polynomial-size binary rational allocation with the proved expectation guarantee.
⟨structured verdict parsed — rendered above⟩
The output resolves the requested approximation question. The mass-to-discrete reduction, LP relaxation, rounding analysis, and finite-bit implementation are correct. I found no major or minor issues.
The discrete instance has exactly \(\tau\) users, with valuations \(c_t(i)=\mu_t b_t(i)\). These valuations are nonnegative, symmetric, explicitly represented, and satisfy \(c_t(0)=0\).
Both directions of the claimed equality \(\mathrm{OPT}=D\) are valid:
This argument uses neither monotonicity nor a lower bound on the positive masses. It also establishes attainment of the mass optimum: a maximizing discrete allocation exists among finitely many bundle assignments and induces an optimal mass allocation.
Finding: Correct.
For the supplied witnessing ordering, the asserted inequality
\[
2|I\cap P_t|\leq\rho
\]
holds for every type \(t\) and every independent set \(I\). The outer maximum with \(1\) in the definition of \(\rho_H\) causes no problem and ensures \(\rho\geq1\).
The LP correctly omits cardinality zero: its welfare contribution is zero, and the constraint \(\sum_i x_{t,i}\leq1\) accommodates an empty allocation.
For a feasible discrete allocation, the identity
\[
2\sum_{u\in P_t}|S_u|
=
\sum_{j=1}^k2|I_j\cap P_t|
\]
counts the same neighbor-channel incidences on both sides. Applying the ordering promise separately to each independent set \(I_j\) proves the LP constraint. Consequently, \(B\geq D=\mathrm{OPT}\).
The rational LP theorem invoked here is applicable: an explicitly represented rational LP can be optimized exactly in polynomial bit complexity, and an optimal rational solution of polynomial encoding length can be returned when a finite optimum exists. The write-up verifies the relevant conditions:
Multiplication of the input rationals to obtain \(c_t(i)\) preserves polynomial encoding length.
Finding: Correct; the theorem application is justified.
When \(B=0\), the empty allocation satisfies the guarantee because \(0\leq\mathrm{OPT}\leq B\).
When \(B>0\), the optimal solution has a positive coordinate, so the minimum positive coordinate \(a\) is defined. For positive coordinates, rounding down gives
\[
p_{t,i}\leq\frac{x_{t,i}}{2\rho},
\qquad
p_{t,i}\geq\frac{x_{t,i}}{2\rho}-2^{-q}
\geq\frac{x_{t,i}}{4\rho}.
\]
For zero coordinates, both bounds hold with equality.
Each request distribution is valid because its total positive-request probability is at most \(1/(2\rho)\leq1/2\). The remaining probability can therefore be assigned to zero.
The finite-bit sampling description is exact: all probabilities have denominator \(2^q\), and cumulative integer intervals implement them using a uniform \(q\)-bit integer. There is no rejection loop or unbounded sampling time.
Finding: Correct.
For each edge, its later endpoint receives only channels absent from its earlier neighbor’s assigned bundle. Thus the endpoints never share a channel.
Every type receives either exactly its requested number of channels or the empty bundle. This exact-cardinality property matters because the valuations need not be monotone.
Finding: Every random outcome is feasible.
For either round, the displayed expectation bound is correct:
\[
\mathbb E\!\left[\sum_{u\in P_t}D_u\right]
\leq
\frac{1}{2\rho}
\sum_{u\in P_t}\sum_{h=1}^k h x_{u,h}
\leq\frac{k}{4}.
\]
The second inequality follows directly from the LP constraint, including its factor of \(2\).
The requests of earlier neighbors are independent of \(D_t\). Conditioning on \(D_t=i\) therefore leaves their distribution unchanged. No independence among greedy acceptance events is assumed or needed.
Small cardinalities. Failure means fewer than \(i\) channels are available, so more than \(k-i\) are blocked. Since \(i\leq k/2\), this implies more than \(k/2\) blocked channels. The number blocked is at most the sum of earlier neighboring requests. Markov’s inequality for this nonnegative sum yields conditional failure probability at most \(1/2\).
Large cardinalities. If every earlier neighboring request is zero, all channels remain available. Thus failure requires at least one positive neighboring request. Since every positive request in this round exceeds \(k/2\),
\[
\sum_{u\in P_t}\Pr(D_u>0)
\leq
\frac{2}{k}\sum_{u\in P_t}\mathbb E[D_u]
\leq\frac12.
\]
The union bound gives the claimed conditional failure probability.
All thresholds, factors, and inequality directions are correct.
Finding: Both success-probability bounds are established.
For every cardinality in the applicable range,
\[
\Pr(|S_t^{(\ell)}|=i)
\geq
p_{t,i}\Pr(t\text{ succeeds}\mid D_t=i)
\geq\frac{x_{t,i}}{8\rho}.
\]
Nonnegativity of the valuations permits summing these lower bounds. The value of the empty bundle is zero, so failed requests introduce no negative contribution.
Returning the better allocation gives pointwise welfare at least the average of the two rounds. Independence between the rounds is unnecessary. Since the ranges partition all positive cardinalities, the calculation yields
\[
\mathbb E[C(S)]
\geq\frac{B}{16\rho}
\geq\frac{\mathrm{OPT}}{16\rho_H}.
\]
The mass allocation induced by the returned discrete allocation has exactly the same welfare.
For \(k=1\), the first range is empty and the second-round analysis remains valid. Zero valuations and an edgeless conflict graph also cause no failure in the argument.
Finding: The requested constant and expectation guarantee are proved.
Polynomial encoding length of \(x\) bounds the bit length of its smallest positive coordinate. Together with the encoding of \(\rho\), this permits a polynomially bounded choice of \(q\), computed by exact arithmetic.
Sampling, cumulative comparisons, channel assignment, and exact welfare comparison all require polynomial time. Each output contains one entry per type, with an input mass and a \(k\)-bit bundle mask. Thus every output has polynomial encoding length and uses the required binary rational masses.
The result establishes a polynomial-time algorithm for the requested approximation guarantee; it does not claim polynomial-time exact optimization.
Finding: The computational and representation requirements are satisfied.
No repair or additional clarification is required.
⟨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.