Answer: NP-hard to approximate within \(c(\ln(1/\epsilon)+\log\tau)\) for a universal constant \(c>0\), even with polynomial-size circuits and dyadic rational data.
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of min-max submodular ranking for multiple agents cannot be approximated within a fac- tor of c · (ln(1/ϵ) + log k) for some constant c > 0 unless P=NP, where ϵ is the minimum non-zero marginal value and k is the number of agents. Now we show a tight approximation for GMSC. The al- gorithm is an LP-based randomized algorithm. Let xe,t be the variable that indicates whether the element e is sched- uled at time t. To reduce the integrality gap, we introduce an exponential number of constraints.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of tests \(U\), a finite type support \(T\) with positive binary-rational masses \(\mu_t\) summing to \(1\), and for each type \(t\) explicitly represented monotone submodular functions \(f_{tj}:2^U\to[0,1]\) with \(f_{tj}(U)=1\) and positive weights \(a_{tj}\), find a permutation \(\pi\) minimizing \(\max_{t\in T}\mu_t\sum_j a_{tj}\operatorname{cov}(f_{tj},\pi)\), where \(\operatorname{cov}(f_{tj},\pi)\) is the first prefix length at which \(f_{tj}\) reaches \(1\).
Let \(U\) be a nonempty set of \(m\) tests. A society is given by its support: a list \(T\) of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type \(t\) has \(q_t\geq1\) monotone submodular functions \(f_{tj}:2^U\to[0,1]\), with \(f_{tj}(U)=1\), and positive binary-rational weights \(a_{tj}\), without any normalization of the weights. Each function is represented by a Boolean circuit that takes the incidence vector of a subset and outputs a binary rational value; the stated function properties are promises.
Let \(L\) be the total input bit length, including circuits, weights, and masses, and let \(Q=\sum_{t\in T}q_t\). Let \(\epsilon\) be the minimum positive difference \(f_{tj}(S')-f_{tj}(S)\) over all functions and \(S\subseteq S'\subseteq U\); set \(\epsilon=1\) if no such difference exists.
A feasible solution is one permutation \(\pi\) of \(U\). Define \(\operatorname{cov}(f,\pi)=\min\{r\in\{1,\ldots,m\}:f(\{\pi(1),\ldots,\pi(r)\})=1\}\) and minimize \(C(\pi)=\max_{t\in T}\mu_t\sum_{j=1}^{q_t}a_{tj}\operatorname{cov}(f_{tj},\pi)\).
Does this problem retain NP-hardness of approximation within \(c(\ln(1/\epsilon)+\log\tau)\) for some universal constant \(c>0\), or admit a polynomial-time approximation with asymptotically smaller dependence on \(\epsilon\) and \(\tau\)? State running times in \(m,\tau,Q,L\).
For discrete agents, min-max submodular ranking is NP-hard to approximate within \(c(\ln(1/\epsilon)+\log k)\) for some constant \(c>0\), where \(k\) is the number of agents. [Source](https://arxiv.org/html/2212.07682)
No result explicitly treating the mass-weighted support formulation above was identified in the source search.
The problem retains the stated NP-hardness of approximation. There is a universal constant \(c>0\) such that approximation within \(c(\ln(1/\epsilon)+\log\tau)\) is NP-hard, even with polynomial-size circuits and dyadic rational data.
This is the usual asymptotic, worst-case hardness statement. At \(\epsilon=1,\tau=1\), the displayed expression vanishes; approximation upper bounds should therefore use \(1+\ln(1/\epsilon)+\log\tau\). Throughout the proof, take \(\log=\ln\); another fixed logarithm base changes only \(c\).
The unrestricted weights are decisive: masses can be absorbed into them exactly. I prove this equivalence and then give explicit circuit reductions establishing hardness of both logarithmic terms.
Define the effective weight \(w_{tj}=\mu_ta_{tj}\). For every permutation \(\pi\),
\(\displaystyle C(\pi)=\max_{t\in T}\sum_{j=1}^{q_t}w_{tj}\operatorname{cov}(f_{tj},\pi).\)
Thus every support instance is an ordinary discrete-agent instance with \(k=\tau\). The functions, \(\epsilon\), feasible permutations, and objective values remain unchanged.
Conversely, consider a discrete-agent instance with \(k\) agents and positive weights \(w_{tj}\). We can give it positive dyadic masses summing to \(1\), preserving every objective value.
For \(k=1\), use mass \(1\). For \(k\geq2\), let \(h=\lceil\log_2 k\rceil\). Assign:
The number of masses is \(k\), and their sum is
\(\displaystyle (2^h-k)2^{-(h-1)}+(2k-2^h)2^{-h}=1.\)
For an agent with mass \(2^{-d_t}\), set \(a_{tj}=2^{d_t}w_{tj}\). Then \(\mu_ta_{tj}=w_{tj}\), exactly.
Consequently, this transformation preserves approximation ratios, \(\tau=k\), and \(\epsilon\). If the discrete input length is \(L_d\), its construction takes
\(\displaystyle O\!\left(L_d+(k+Q)\log(k+1)\right)\)
bit operations and produces an encoding of that size. This also handles the interpretation of “binary-rational” as requiring dyadic rationals.
The cited paper’s Theorem 4 therefore transfers whenever its hard instances have polynomial-size circuit representations. The following reductions establish that representation requirement directly. [Chen et al., Theorem 4](https://arxiv.org/html/2212.07682)
Use the standard set-cover hardness theorem: for every fixed \(\alpha>0\), approximation within \((1-\alpha)\ln p\), where \(p\) is the universe cardinality, is NP-hard. We need only the weaker consequence with factor \(\tfrac12\ln p\). [Dinur–Steurer, Corollary 1.5 and Section 6.2](https://www.dsteurer.org/paper/productgames.pdf)
Let \(E=\{e_1,\ldots,e_p\}\) and \(\mathcal C=\{C_1,\ldots,C_s\}\) be a feasible set-cover instance, meaning \(\bigcup_{\ell=1}^s C_\ell=E\). Write \(r^\star\) for its minimum cover cardinality.
Create \(m=s\) tests, one for each set. For every \(e_i\), create a type with one function:
\(\displaystyle f_i(S)=\mathbf 1\!\left\{e_i\in\bigcup_{\ell\in S}C_\ell\right\}.\)
This function satisfies all promises:
Choose the dyadic masses from Section 1 and set \(a_{i1}=1/\mu_i\). Therefore every effective weight is \(1\), and
\(\displaystyle C(\pi)=\max_i\operatorname{cov}(f_i,\pi).\)
The first \(C(\pi)\) tests cover every element of \(E\). Conversely, putting any set cover of cardinality \(r\) first produces objective at most \(r\). Thus
\(\displaystyle \operatorname{OPT}=r^\star.\)
Extracting that prefix converts a ranking approximation into a set-cover approximation with the same ratio. Since \(\tau=p\) and \(\epsilon=1\), this proves logarithmic support-size hardness.
If “types” must be behaviorally distinct, first delete duplicate incidence rows. This preserves the set-cover optimum and only decreases \(\tau\), so a hypothetical \(c\ln\tau\) guarantee still yields a \(c\ln p\) guarantee for the original instance.
The construction has \(\tau=Q=p\), and its circuit encoding and construction time are polynomial in the explicit set-cover input length.
Again start with a feasible set-cover instance on \(p\geq4\) elements and \(s\) sets. Choose the smallest power of two \(N\) satisfying \(N\geq p+2\).
Add \(N-p\) new coverage elements, partitioned into a singleton \(\{z\}\) and a nonempty set \(D\). Add two tests: test \(u_z\) covers only \(z\), and test \(u_D\) covers exactly \(D\). Original tests cover their original sets and no new elements.
Use one type, with mass \(1\), one function, and weight \(1\). Its function is the fraction of the enlarged universe covered:
\(\displaystyle f(S)=\frac{\left|\bigcup_{\ell\in S\cap\{1,\ldots,s\}}C_\ell\right|+\mathbf 1_{\{u_z\in S\}}+|D|\mathbf 1_{\{u_D\in S\}}}{N}.\)
Each coverage-element indicator has diminishing marginals, as proved in Section 2. Their sum, divided by \(N>0\), is therefore monotone and submodular. Feasibility gives \(f(U)=1\).
All values are multiples of \(1/N\), and adding \(u_z\) to the empty set increases the value by exactly \(1/N\). Hence
\(\displaystyle \epsilon=1/N.\)
Because \(N\) is a power of two, all outputs are dyadic. OR gates compute the coverage indicators; a binary adder computes their count. The resulting circuit has polynomial size.
Every covering prefix must contain both added tests and enough original tests to cover \(E\). Conversely, an optimal original cover together with the two added tests covers everything. Therefore
\(\displaystyle \operatorname{OPT}=r^\star+2.\)
Suppose a ranking algorithm has approximation ratio \(\rho\). Removing the two added tests from its first covering prefix gives an original set cover of cardinality at most
\(\displaystyle \rho(r^\star+2)-2\leq3\rho r^\star,\)
where \(r^\star\geq1\) justifies \(r^\star+2\leq3r^\star\).
Here \(\tau=1\), so a guarantee \(c(\ln(1/\epsilon)+\ln\tau)\) means \(\rho=c\ln N\). Minimality of \(N\) and \(p\geq4\) give
\(\displaystyle N<2(p+2)\leq p^2,\qquad \ln N\leq2\ln p.\)
The extracted set cover consequently has approximation ratio at most \(6c\ln p\). Taking, for example, \(c=1/24\) would yield a \(\tfrac14\ln p\) approximation, contradicting the set-cover hardness theorem.
This construction has \(m=s+2\) and \(\tau=Q=1\), and again takes polynomial time in the explicit set-cover input length.
Together, the reductions establish the requested hardness for a universal constant \(c>0\). They also establish the two separate obstructions:
Therefore, unless \(\mathrm P=\mathrm{NP}\), no deterministic algorithm running in \(\operatorname{poly}(m,\tau,Q,L)\) can guarantee a ratio \(o(\ln(1/\epsilon)+\log\tau)\) uniformly as that expression grows. This does not assert hardness for every prescribed parameter pair.
For comparison, a direct polynomial approximation is available. Absorb the masses into \(w_{tj}\), stack all functions into one weighted submodular-ranking instance, and run normalized greedy. The single-agent guarantee is \(\beta=4\ln(1/\epsilon)+8\). [Chen et al., Theorem 2 with one agent](https://arxiv.org/html/2212.07682)
To check applicability, any nonconstant function can be normalized as
\(\displaystyle g(S)=\frac{f(S)-f(\varnothing)}{1-f(\varnothing)}.\)
This preserves cover times and submodularity and cannot decrease its positive differences. Its normalized-greedy scores equal those of \(f\). Functions with \(f(\varnothing)=1\) are constant \(1\); their cover-time contributions are permutation-independent and can be added afterward.
Let \(G(\pi)=\sum_{t,j}w_{tj}\operatorname{cov}(f_{tj},\pi)\). For every permutation,
\(\displaystyle C(\pi)\leq G(\pi)\leq\tau C(\pi).\)
If \(\pi^\star\) minimizes \(C\), normalized greedy returns \(\pi_{\mathrm{NG}}\) satisfying
\(\displaystyle C(\pi_{\mathrm{NG}})\leq G(\pi_{\mathrm{NG}})\leq\beta\min_\pi G(\pi)\leq\beta G(\pi^\star)\leq\tau\beta C(\pi^\star).\)
The algorithm uses \(O(m^2Q)\) circuit evaluations and does not need to compute \(\epsilon\). A conservative bound, using schoolbook exact rational arithmetic, is
\(\displaystyle O\!\left((m^2Q+\tau)(QL+m+\log(m+1))^2\right)\)
bit operations: individual score terms have \(O(L)\)-bit numerators and denominators, and a sum of at most \(Q\) terms has \(O(QL)\)-bit representation.
Any permutation is also an \(m\)-approximation: writing \(W=\max_t\sum_jw_{tj}\), every feasible objective lies between \(W\) and \(mW\). Returning the better of that permutation and normalized greedy gives ratio
\(\displaystyle \min\{m,\tau(4\ln(1/\epsilon)+8)\}\)
within the same polynomial running-time bound.
⟨structured verdict parsed — rendered above⟩
The prover resolves the intended worst-case hardness question. Both reductions are valid, the approximation constants check out, and the polynomial-time comparison algorithm has the stated guarantee. I found no substantive or expositional gap requiring repair.
The output explicitly interprets the hardness claim asymptotically. This correctly avoids treating the vanishing expression at \(\epsilon=1,\tau=1\) as a meaningful approximation factor.
It also correctly distinguishes worst-case parameter dependence from hardness at every prescribed parameter pair. The two separate reductions suffice to exclude a uniformly asymptotically smaller dependence; they do not establish simultaneous hardness for arbitrary fixed values of both parameters.
The identity \(w_{tj}=\mu_ta_{tj}\) preserves every objective value, since each mass multiplies the entire corresponding type’s weighted sum. Positivity is preserved. Neither the functions nor their cover times nor \(\epsilon\) changes.
The converse construction is correct:
The case \(k=1\) is handled separately. Multiplication by powers of two preserves dyadic data when the original weights are dyadic.
The stated encoding and construction bound is consistent with copying the discrete instance and adding \(O(\log(k+1))\) bits per mass and weight. Thus this is an approximation-preserving polynomial transformation.
The cited discrete-agent hardness statement agrees with [Chen et al., Theorem 4](https://arxiv.org/html/2212.07682). The explicit reductions below independently establish the circuit-representation requirement, so the conclusion does not rest on an unspecified oracle representation.
The reduction from feasible set cover satisfies all input promises.
For each element, the corresponding function is a coverage indicator. Its marginal is either zero or one, and becomes zero once that element is covered. The diminishing-marginal argument therefore establishes submodularity. Feasibility supplies \(f_i(U)=1\), and OR circuits provide explicit polynomial-size representations.
Each function has value zero on the empty set and value one on the full test set. Consequently positive differences exist, and every positive difference equals one. Thus \(\epsilon=1\) exactly.
The reciprocal weights cancel the assigned masses, making the objective the latest first-cover time of any universe element. The first \(C(\pi)\) tests therefore form a cover. Conversely, placing any cover first gives objective at most its cardinality. These two directions justify \(\operatorname{OPT}=r^\star\) and preserve approximation ratios upon prefix extraction.
The set-cover hardness invoked is supported by [Dinur–Steurer, Corollary 1.5 and Section 6.2](https://www.dsteurer.org/paper/productgames.pdf). The weaker factor used in the argument is sufficient.
The optional removal of duplicate incidence rows preserves feasibility and optimum. Decreasing the support size can only decrease the claimed logarithmic guarantee. No defect arises from the support interpretation.
The padding construction is valid. Since \(N\geq p+2\), the added elements can be partitioned into the singleton and a nonempty set \(D\).
The function is a positive rescaling of a sum of coverage indicators. The stated monotonicity and submodularity reasoning applies, its values lie in the required interval, and the full test set covers every enlarged-universe element.
The calculation of \(\epsilon\) is exact: every value is a multiple of \(1/N\), while adding \(u_z\) to the empty set achieves a positive difference of precisely \(1/N\).
Both added tests are indispensable because their elements occur in no other test. Every covering prefix must therefore contain them and an original set cover. Conversely, an optimal original cover plus the two added tests covers the enlarged universe. This establishes \(\operatorname{OPT}=r^\star+2\).
The extraction bound is correct. Removing the two mandatory tests leaves a cover of cardinality at most \(\rho(r^\star+2)-2\), and the subsequent bound by \(3\rho r^\star\) follows from \(r^\star\geq1\).
The numerical estimates also check:
The OR and counting circuits have polynomial size, and division by the power of two produces dyadic outputs. All representation promises are preserved.
The chosen universal constant works for both reductions. A hypothetical guarantee with the claimed sum would apply to each restricted family, where one logarithmic term vanishes.
Likewise, a uniform little-oh guarantee would restrict to an asymptotically smaller logarithmic guarantee on either family. The stated exclusion of deterministic polynomial-time algorithms therefore follows unless \(\mathrm P=\mathrm{NP}\).
The output correctly avoids claiming hardness at every parameter pair.
The single-agent normalized-greedy factor agrees with [Chen et al., Theorem 2 specialized to one agent](https://arxiv.org/html/2212.07682).
For a nonconstant function, the normalization denominator is positive. The transformation preserves the full-coverage condition, monotonicity, and submodularity. Positive differences cannot decrease, and the normalized-greedy scores are unchanged.
If \(f(\varnothing)=1\), monotonicity and the range restriction force the function to be constant one. Under the task’s cover-time convention, its contribution is permutation-independent. Removing such functions and adding their contributions afterward is legitimate. If all functions are constant, every permutation is optimal.
The inequalities \(C(\pi)\leq G(\pi)\leq\tau C(\pi)\) follow from positivity of the type costs. The displayed approximation chain consequently proves the claimed factor \(\tau(4\ln(1/\epsilon)+8)\).
The arbitrary-permutation bound is also correct: every cover time lies between one and \(m\), giving \(W\leq C(\pi)\leq mW\). Selecting the better candidate therefore gives the stated minimum of the two approximation factors.
The \(O(m^2Q)\) circuit-evaluation count is consistent with evaluating every remaining test against every function at each greedy step.
Circuit outputs and individual rational score terms have \(O(L)\)-bit representations. Exact sums of at most \(Q\) terms admit the stated \(O(QL)\) bit bound. The conservative squared arithmetic bound accommodates circuit evaluation, score formation, comparisons, and objective evaluation. It is polynomial in \(m,\tau,Q,L\), as requested.
Both hardness constructions are polynomial in the explicit set-cover input length.
Required feedback: none. The write-up establishes its claimed result without a blocking issue.
⟨structured verdict parsed — rendered above⟩finishes_text_not_done
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.