Answer: The requested simultaneous approximation is polynomial-time solvable; one schedule achieves a simultaneous \(1/2\)-approximation.
Theorem 5.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSIMAPPROX produces solutions that simulta- neously α-approximate f-MAXCOVERAGE for all f, in poly- nomial time, for α = 1−1/e 2 · ( 1 1+log2 T −1 T ) ∈Ω(1/ log T).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many complete participant types \(p\) with rational masses \(\mu_p\), \(k\) tables, \(T\) sessions, and mass-normalized representativeness constraints, choose trajectory masses \(x_{p,\sigma} \ge 0\) for \(\sigma \in [k]^T\) with \(\sum_{\sigma} x_{p,\sigma} = \mu_p\) and feasible per-session table masses, so that \(\Phi_f(x) = 1/2 \sum_{p,q} \sum_{\sigma,\sigma'} x_{p,\sigma} x_{q,\sigma'} f(|\{r : \sigma_r = \sigma'_r\}|)\) simultaneously \(\alpha_T\)-approximates \(\max_{x'} \Phi_f(x')\) for every monotone concave saturation function \(f\) with \(f(0) = 0\).
A society is given by its support: \(\tau\) distinct complete types \(p\in\{0,1\}^m\), describing possession of \(m\) features, with positive binary-rational masses \(\mu_p\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
There are integers \(k\ge1\) tables and \(T\ge2\) sessions, and binary-rational feature quotas \(0\le\ell_j\le u_j\le1/k\), identical across tables and sessions.
A schedule consists of divisible trajectory masses \(x_{p,\sigma}\ge0\), where \(\sigma\in\{1,\ldots,k\}^T\), with \(\sum_\sigma x_{p,\sigma}=\mu_p\). For every session \(r\), table \(a\), and feature \(j\), require \(\sum_{p,\sigma:\sigma_r=a}x_{p,\sigma}=1/k\) and \(\ell_j\le\sum_{p,\sigma:\sigma_r=a}p_jx_{p,\sigma}\le u_j\). Promise feasibility.
A saturation function is \(f:\{0,\ldots,T\}\to\mathbb R_{\ge0}\), nondecreasing and discretely concave, with \(f(0)=0\). Define \(c(\sigma,\sigma')=|\{r:\sigma_r=\sigma'_r\}|\) and \(\Phi_f(x)=\tfrac12\sum_{p,q}\sum_{\sigma,\sigma'}x_{p,\sigma}x_{q,\sigma'}f(c(\sigma,\sigma'))\), including equal types and equal trajectories; masses describe an atomless population.
Set \(\alpha_T=\tfrac{1-1/e}{2}\bigl(\tfrac1{1+\log_2 T}-\tfrac1T\bigr)\). Algorithmic schedules are represented by a list of nonzero rational trajectory masses.
Is there an algorithm running in time polynomial in \(m,\tau,k,T,L\) that, without receiving \(f\), constructs one feasible schedule \(x\) satisfying \(\Phi_f(x)\ge\alpha_T\max_{x'\text{ feasible}}\Phi_f(x')\) for every saturation function \(f\), or is achieving this simultaneous guarantee NP-hard?
For discrete concave coverage with an explicitly listed collection of selectable sets and repetitions allowed, SIMAPPROX achieves this simultaneous factor in polynomial time; discrete table allocation instead uses ILP subproblems, and partition feasibility is NP-hard. [Barrett et al.](https://procaccia.info/wp-content/uploads/2022/06/deliberation.pdf)
No result settling the trajectory-mass problem defined here was found in the literature search.
The requested algorithm exists. In fact, it constructs a feasible schedule satisfying the stronger guarantee
\( \Phi_f(x)\ge \tfrac12\max_{x'\text{ feasible}}\Phi_f(x') \)
for every admissible saturation function \(f\), without receiving \(f\).
The proof uses divisibility and the identical quotas across tables. It does not require solving the discrete partition problem.
For each feature \(j\), define its total population mass by
\( M_j=\sum_p\mu_p p_j \).
Summing the feature constraints over the \(k\) tables in any session shows that feasibility implies
\( k\ell_j\le M_j\le ku_j \).
Thus, by the feasibility promise,
\( \ell_j\le M_j/k\le u_j \).
Let \(y\) be any probability distribution on trajectories with uniform session marginals:
\( \sum_{\sigma:\sigma_r=a}y_\sigma=1/k \)
for every session \(r\) and table \(a\). Define
\( x_{p,\sigma}=\mu_p y_\sigma \).
These masses sum to \(\mu_p\) for each type. Each table has mass \(1/k\), and its feature-\(j\) mass is
\( \sum_{p,\sigma:\sigma_r=a}p_jx_{p,\sigma}=M_j/k \).
Consequently, this schedule is feasible.
Conversely, every feasible schedule induces a trajectory distribution
\( y_\sigma=\sum_p x_{p,\sigma} \)
with uniform session marginals. Its objective depends only on this distribution:
\( \Phi_f(x)=\tfrac12\sum_{\sigma,\sigma'}y_\sigma y_{\sigma'}f(c(\sigma,\sigma')) \).
Equivalently, if \(\Sigma,\Sigma'\) are independent trajectories drawn from \(y\), and \(C=c(\Sigma,\Sigma')\), then
\( \Phi_f(x)=\tfrac12\mathbb E[f(C)] \).
Therefore, the attainable objectives are exactly those obtained from trajectory distributions with uniform session marginals.
We construct a rational trajectory distribution \(y\) satisfying
\( \Pr(\Sigma_r=a)=1/k \)
and, for distinct sessions \(r,s\),
\( \Pr(\Sigma_r=a,\Sigma_s=b)=1/k^2 \).
The construction maintains a distribution on prefixes and extends it one session at a time.
For the first session, give each label mass \(1/k\). Suppose that a distribution on \(r-1\) sessions has positive masses \(v_i\) on prefixes \(\sigma^{(i)}\), indexed by \(i\in\{1,\ldots,M\}\), and already has the required pairwise independence.
Introduce variables \(z_{i,b}\), representing the mass assigned to prefix \(\sigma^{(i)}\) followed by label \(b\). Impose the following rational linear constraints:
This polytope is nonempty: \(z_{i,b}=v_i/k\) satisfies every constraint. It is bounded because \(0\le z_{i,b}\le v_i\).
Choose a vertex of this polytope and retain its positive variables as the new prefix distribution. The prefix-mass equations preserve all old marginals and pair distributions. The last family of equations gives independence between the new session and every old session. Summing those equations over \(a\) also gives the new session’s uniform marginal.
There are \(M+(r-1)k^2\) equality constraints. A vertex has at most this many positive variables.
Indeed, write the equalities as \(Az=b\). If the columns indexed by positive variables were linearly dependent, there would be a nonzero vector \(h\), supported on those variables, with \(Ah=0\). For sufficiently small positive \(\varepsilon\), both \(z+\varepsilon h\) and \(z-\varepsilon h\) would remain nonnegative and feasible, contradicting that \(z\) is a vertex.
Writing \(M_r\) for the support size after session \(r\), we obtain
\( M_1=k \)
and
\( M_r\le M_{r-1}+(r-1)k^2 \).
Hence the final distribution has support at most
\( M_T\le k+\binom{T}{2}k^2 \).
We use the standard theorem that rational linear programs can be solved exactly in time polynomial in their binary encoding length. See [Khachiyan’s polynomial algorithms for linear programming](https://www.mathnet.ru/eng/zvmmf5239). A vertex of a nonempty bounded rational polytope can be obtained by successively minimizing its coordinates: each minimization restricts to an optimal face, and after all coordinates have been fixed the resulting singleton is a vertex.
Here every extension has polynomially many variables and constraints. We also verify that rational encodings remain polynomially bounded across extensions.
Suppose that all old masses have common denominator \(D_{r-1}\). Every right-hand side then has denominator dividing \(D_{r-1}k^2\). At a vertex with \(d\) positive variables, their columns are independent, so selecting \(d\) suitable rows gives an invertible matrix \(B\) with entries in \(\{0,1\}\). Cramer’s rule shows that the new masses have a common denominator dividing
\( D_{r-1}k^2|\det B| \).
Hadamard’s inequality gives
\( |\det B|\le d^{d/2} \),
where
\( d\le M_{r-1}+(r-1)k^2\le k+\binom{T}{2}k^2 \).
Thus each extension increases the common denominator’s bit length by at most
\( 2\log_2 k+\tfrac d2\log_2 d \).
There are only \(T-1\) extensions, so all mass encodings have polynomial bit length. Since every mass lies in \([0,1]\), its numerator has the same bound.
The intermediate coordinate minimizations also have polynomial encoding length: each intermediate optimum is attained at a vertex of the original extension polytope, whose coordinates have the determinant bound just established.
Finally, output \(x_{p,\sigma}=\mu_p y_\sigma\). There are at most
\( \tau\bigl(k+\binom{T}{2}k^2\bigr) \)
positive type–trajectory masses, each with polynomial bit length. The entire construction therefore runs in time polynomial in \(m,\tau,k,T,L\).
Fix the constructed distribution, and draw independent trajectories \(\Sigma,\Sigma'\). Define
\( I_r=\mathbf 1_{\{\Sigma_r=\Sigma'_r\}} \)
and
\( C=\sum_{r=1}^T I_r \).
Uniform marginals imply
\( \mathbb E[I_r]=\sum_{a=1}^k(1/k)^2=1/k \).
For distinct sessions \(r,s\), independence of the two sampled trajectories and pairwise uniformity within each trajectory imply
\( \mathbb E[I_rI_s]=\sum_{a,b}\Pr(\Sigma_r=a,\Sigma_s=b)^2=k^2(1/k^2)^2=1/k^2 \).
Consequently, for the collision count \(D_h=\sum_{r=1}^h I_r\) over the first \(h\) sessions,
\( \mathbb E[D_h]=h/k \)
and
\( \mathbb E[D_h(D_h-1)]=h(h-1)/k^2 \).
The inclusion of equal trajectories in the objective is fully accounted for by these independent draws.
For an integer \(s\in\{1,\ldots,T\}\), define
\( g_s(z)=\min(z,s) \).
We first prove the pointwise inequality
\( \min(z,s)\ge z-\frac{z(z-1)}{2s} \)
for every nonnegative integer \(z\).
If \(z\le s\), the subtracted term is nonnegative, so the inequality follows. If \(z\ge s\), put \(d=z-s\). The inequality is equivalent to
\( z(z-1)-2s(z-s)\ge0 \),
and its left-hand side equals
\( s(s-1)+d(d-1)\ge0 \),
because \(s\) and \(d\) are nonnegative integers with \(s\ge1\).
Now choose
\( h=\min(T,sk) \)
and write
\( \nu=h/k=\min(T/k,s) \).
Since \(D_h\le C\), the moment identities give
\( \mathbb E[\min(C,s)]\ge\mathbb E[\min(D_h,s)]\ge\nu-\frac{h(h-1)}{2sk^2} \).
Furthermore,
\( \frac{h(h-1)}{2sk^2}\le\frac{\nu^2}{2s}\le\frac{\nu}{2} \),
where the last inequality uses \(\nu\le s\). Hence the constructed schedule satisfies
\( \Phi_{g_s}(x)\ge\nu/4 \).
For comparison, consider any feasible schedule \(x'\) and its collision count \(C'\). Its uniform session marginals give
\( \mathbb E[C']=T/k \).
Because \(\min(C',s)\le C'\) and \(\min(C',s)\le s\),
\( \Phi_{g_s}(x')\le\tfrac12\min(T/k,s)=\nu/2 \).
Therefore, for every threshold \(s\) and every feasible \(x'\),
\( \Phi_{g_s}(x)\ge\tfrac12\Phi_{g_s}(x') \).
Let \(f\) be any admissible saturation function. Define its increments by
\( \Delta_s=f(s)-f(s-1) \)
for \(s\in\{1,\ldots,T\}\), and set \(\Delta_{T+1}=0\).
Monotonicity and discrete concavity give
\( \Delta_1\ge\Delta_2\ge\cdots\ge\Delta_T\ge0 \).
Thus the coefficients
\( w_s=\Delta_s-\Delta_{s+1} \)
are nonnegative.
For every integer \(z\in\{0,\ldots,T\}\),
\( f(z)=\sum_{s=1}^T w_s\min(z,s) \).
To verify this identity, both sides vanish at zero, and the increment of the right-hand side from \(z-1\) to \(z\) is
\( \sum_{s=z}^T w_s=\Delta_z \).
Linearity of the objective in the saturation function now yields, for every feasible \(x'\),
\( \Phi_f(x)=\sum_{s=1}^T w_s\Phi_{g_s}(x)\ge\tfrac12\sum_{s=1}^T w_s\Phi_{g_s}(x')=\tfrac12\Phi_f(x') \).
The feasible set is a nonempty compact polytope, and the objective is continuous, so its maximum exists. Consequently,
\( \Phi_f(x)\ge\tfrac12\max_{x'\text{ feasible}}\Phi_f(x') \).
The construction depends only on \(k,T\) and the type masses; it never receives \(f\).
For \(T\ge2\),
\( \alpha_T\le(1-1/e)/4<1/2 \).
Thus the polynomial-time construction satisfies the requested simultaneous guarantee, with a stronger factor.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The construction produces one feasible rational schedule, independently of \(f\), with a simultaneous approximation factor of \(1/2\). The support size, running time, and output bit length are polynomial in the parameters specified in USER_TASK. I found no major or minor mathematical issues.
Summing the feature quotas over all tables gives the necessary bounds \(k\ell_j\le M_j\le ku_j\). Thus the feasibility promise implies \(\ell_j\le M_j/k\le u_j\).
For any trajectory distribution \(y\) with uniform session marginals, the proposed lift \(x_{p,\sigma}=\mu_p y_\sigma\) preserves every type mass, gives each table mass \(1/k\), and gives each table feature mass \(M_j/k\). All constraints are therefore satisfied.
Conversely, aggregating any feasible schedule over types produces such a distribution \(y\). Because the objective’s kernel depends only on trajectories, summing over types yields exactly the stated objective in \(y\). Both directions are established, so this is an exact reduction of attainable objectives.
The initial distribution has uniform marginals. At every subsequent extension, \(z_{i,b}=v_i/k\) satisfies the displayed equalities because the old session marginals are uniform. Nonnegativity and the prefix-mass equations also establish boundedness.
The prefix-mass equations preserve the entire old prefix distribution, hence all previously established marginals and pair distributions. The remaining equations establish the required joint probabilities for each old session and the new session. Summing over the old label gives the new marginal \(1/k\).
This induction works for every integer \(k\ge1\); it does not require \(k\) to be a prime power.
The argument using a nonzero dependence vector among positive columns is valid: sufficiently small perturbations in both directions preserve nonnegativity and all equalities, contradicting extremality.
Consequently, the number of positive variables is at most the number of equality constraints. Redundancies among those constraints only strengthen this bound. The recurrence therefore gives exactly the claimed upper bound
\(M_T\le k+\binom{T}{2}k^2\).
The invoked rational linear-programming theorem supplies exact optimization in polynomial time for explicitly encoded rational constraints and objectives. Here every coordinate objective is rational, and every feasible region encountered is a nonempty bounded rational polytope. Thus the relevant hypotheses are satisfied. The supplied reference is [Khachiyan’s polynomial linear-programming paper](https://www.mathnet.ru/eng/zvmmf5239).
Successive coordinate minimizations restrict to nonempty optimal faces. Fixing all coordinates leaves a singleton face, which is a vertex of the original extension polytope. There are only polynomially many coordinates to minimize.
For the bit-length argument, the independent positive columns admit an invertible square row submatrix \(B\). Its entries are indeed in \(\{0,1\}\). Cramer’s rule gives the stated common-denominator divisor, and Hadamard’s bound gives the claimed logarithmic growth estimate.
The bound on \(d\) is polynomial in \(k,T\), and there are only \(T-1\) extensions. Thus denominator and numerator bit lengths remain polynomial. The same reasoning covers intermediate coordinate optima: each is attained at a vertex of an optimal face, hence at a vertex of the original polytope.
Finally, multiplication by the input masses \(\mu_p\) preserves polynomial bit length. The stated bound on the number of output entries is correct; including the length-\(T\) trajectories also leaves the total output length polynomial. The argument establishes polynomial time in the numerical parameters requested by the task.
Independence of the two trajectory draws and uniform session marginals give \(\mathbb E[I_r]=1/k\).
For distinct sessions, the constructed pairwise uniformity gives
\(\mathbb E[I_rI_s]=k^2(1/k^2)^2=1/k^2\).
Expanding \(D_h(D_h-1)\) over ordered distinct session pairs yields the stated factorial second moment.
No higher-order independence is asserted or needed. Equal trajectories and equal types are included correctly through the independent-draw interpretation of the objective.
The pointwise inequality is correct for every nonnegative integer \(z\). In the case \(z\ge s\), the stated expansion is exact:
\(z(z-1)-2s(z-s)=s(s-1)+d(d-1)\).
Both terms are nonnegative for the integer ranges used. The cases \(z=0\), \(z=s\), and \(s=1\) are covered.
The chosen \(h=\min(T,sk)\) is an integer between \(1\) and \(T\), and \(\nu=h/k=\min(T/k,s)\). Monotonicity of the truncation and \(D_h\le C\) justify its use. The moment substitution and the bounds
\(h(h-1)/(2sk^2)\le\nu^2/(2s)\le\nu/2\)
are correct.
Therefore the constructed schedule achieves \(\Phi_{g_s}(x)\ge\nu/4\). For every feasible competitor, uniform marginals imply \(\mathbb E[C']=T/k\), giving \(\Phi_{g_s}(x')\le\nu/2\). The resulting simultaneous factor \(1/2\) is correct.
Discrete concavity and monotonicity give nonnegative, nonincreasing increments. With the stated terminal convention, all coefficients \(w_s\) are nonnegative.
The truncation decomposition is verified correctly by comparing values at zero and successive increments. Linearity then permits summing the truncation inequalities against these coefficients.
Crucially, the proof compares every truncation against the same arbitrary feasible \(x'\). It does not interchange maximization and summation. Consequently, it establishes the claimed inequality for every \(f\) using the single constructed schedule.
Compactness and continuity justify taking a maximizing competitor. The identically zero saturation function is also covered.
For \(T\ge2\), \(1+\log_2 T\ge2\), so the asserted upper bound \(\alpha_T\le(1-1/e)/4<1/2\) holds. Since all objective values are nonnegative, the stronger guarantee implies the requested one.
The case \(k=1\) satisfies the construction and calculations. Positive type masses and arbitrary support sizes introduce no additional restriction. No evaluation or encoding of the possibly real-valued function \(f\) is required.
No repair or additional clarification is needed to make the mathematical argument verifiable.
⟨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.