Answer: Exactly solvable in polynomial time; hence a polynomial-time \(N\)-approximation exists.
Theorem 1.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe solution of algorithm 1 is within a bound n of the optimal. That is, given that V1 is the system welfare of the solution of algorithm 1 and V ∗the optimal solution: V ∗ V1 ≤n PROOF. Let ⟨s∗ i ⟩n i=1 be the optimal state vector (that is, the vector contains the states of all sensor agents). For 1 ≤ j ≤m, let C∗ j be the coalition of sensors that track target tj associated with the optimal solution.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite target set \(J\), sensor types \(a\in\{1,\ldots,\tau\}\) with rational masses \(\mu_a\), finite mode sets \(S_a\), rational mode costs \(c_{a,s}\), visibility indicators \(\mathrm{vis}(a,s,j)\), and rational monotone concave piecewise-linear target valuations \(F_j\) over type masses, find an allocation \(x_{a,s}\ge 0\) with \(\sum_{s\in S_a}x_{a,s}=\mu_a\) that maximizes \(\sum_{j\in J}F_j(q_j)-\sum_a\sum_{s\in S_a}c_{a,s}x_{a,s}\), where \(q_{a,j}=\sum_{s:\mathrm{vis}(a,s,j)=1}x_{a,s}\).
A society is given by its support: the list of \(\tau\) sensor types with positive binary-rational masses \(\mu_a\); \(\tau\) is the support size, not the number of possible types. Masses measure sensor quantities and are not normalized; write \(N=\sum_a\mu_a\geq1\).
There are \(m\geq1\) targets \(J\). Each type has an explicitly listed finite mode set \(S_a\), nonnegative rational per-unit costs \(c_{a,s}\), and visibility indicators \(\mathrm{vis}(a,s,j)\in\{0,1\}\). Every type has a sleep mode \(0\) with zero cost and no visibility.
Each valuation \(F_j:\prod_a[0,\mu_a]\to\mathbb R_{\geq0}\) is coordinatewise monotone, concave, piecewise-linear, and satisfies \(F_j(0)=0\) and \(F_j(u+v)\leq F_j(u)+F_j(v)\) whenever \(u,v,u+v\) lie in its domain. It is encoded explicitly as the minimum of finitely many rational affine functions.
A feasible allocation has \(x_{a,s}\geq0\) and \(\sum_{s\in S_a}x_{a,s}=\mu_a\). Set \(q_j=(q_{a,j})_{a=1}^{\tau}\), where \(q_{a,j}=\sum_{s:\mathrm{vis}(a,s,j)=1}x_{a,s}\), and \(W(x)=\sum_{j\in J}F_j(q_j)-\sum_a\sum_{s\in S_a}c_{a,s}x_{a,s}\). A mode contributes its entire allocated mass to every visible target, while its cost is charged once.
Let \(V^*=\max_x W(x)\), \(K=\sum_a|S_a|\), and \(R\) be the total number of listed affine functions; \(L\) is the total binary input length.
Does this problem admit an \(N\)-approximation, meaning an allocation with \(W(x)\geq V^*/N\), in time polynomial in \(m,\tau,K,R,L\), or is attaining this guarantee NP-hard?
For discrete sensors with monotone subadditive coalition values and zero-cost sleep, a polynomial-time greedy algorithm guarantees \(W\geq V^*/n\), where \(n\) is the number of sensors ([Dang et al., 2006](https://cdn.aaai.org/AAAI/2006/AAAI06-101.pdf)).
No result settling this approximation question for the exact mass model above was identified in the search.
The problem is exactly solvable in time polynomial in \(m,\tau,K,R,L\). Consequently, it admits the requested \(N\)-approximation.
The proof uses the continuous allocation variables and the explicitly listed affine functions to construct a linear program.
For each target \(j\), let \(r_j\) denote the number of listed affine functions, so that \(\sum_{j\in J}r_j=R\). Write the given representation as
\(F_j(u)=\min_{1\leq \ell\leq r_j}\left(b_{j,\ell}+\sum_{a=1}^{\tau}d_{j,\ell,a}u_a\right),\)
where all coefficients are rational.
Introduce allocation variables \(x_{a,s}\), visibility variables \(q_{a,j}\), and one value variable \(t_j\) for each target. Consider the linear program with objective
\(\displaystyle \max\ \sum_{j\in J}t_j-\sum_{a=1}^{\tau}\sum_{s\in S_a}c_{a,s}x_{a,s},\)
subject to the following constraints:
\(x_{a,s}\geq 0.\)
\(\displaystyle \sum_{s\in S_a}x_{a,s}=\mu_a.\)
\(\displaystyle q_{a,j}=\sum_{s\in S_a}\mathrm{vis}(a,s,j)x_{a,s}.\)
\(t_j\geq 0.\)
\(\displaystyle t_j\leq b_{j,\ell}+\sum_{a=1}^{\tau}d_{j,\ell,a}q_{a,j}.\)
Constraints 1–3 imply \(0\leq q_{a,j}\leq\mu_a\): the visibility sum contains a subset of the nonnegative allocation variables whose total is \(\mu_a\). Thus every \(q_j\) lies in the stated domain of \(F_j\).
The same allocation variable enters the visibility equation of every target visible in its mode. Its cost appears once in the objective. Hence the formulation preserves both simultaneous visibility and the prescribed cost accounting.
Let \(P^*\) be the linear program’s optimal value. We prove \(P^*=V^*\).
Every feasible allocation has a lift with equal objective value. Given a feasible allocation \(x\), define \(q\) by constraint 3 and set \(t_j=F_j(q_j)\). Nonnegativity of \(F_j\) gives constraint 4. Because \(F_j\) is the minimum of the listed affine functions, constraint 5 holds for every \(\ell\). The resulting linear programming objective equals \(W(x)\).
The allocation region is a nonempty compact product of simplices. Each \(F_j\) is continuous, being a finite minimum of affine functions. Therefore \(W\) attains its maximum, and lifting a maximizing allocation gives \(P^*\geq V^*\).
Every feasible linear programming point has objective at most its allocation’s welfare. For any feasible \((x,q,t)\), constraint 5 gives
\(\displaystyle t_j\leq\min_{1\leq\ell\leq r_j}\left(b_{j,\ell}+\sum_a d_{j,\ell,a}q_{a,j}\right)=F_j(q_j).\)
Consequently,
\(\displaystyle \sum_j t_j-\sum_{a,s}c_{a,s}x_{a,s}\leq W(x)\leq V^*.\)
This proves \(P^*\leq V^*\), and therefore \(P^*=V^*\). In particular, the allocation component of any optimal linear programming solution satisfies \(W(x)=V^*\).
The formulation has \(K+m\tau+m\) variables, \(\tau+m\tau\) equality constraints, and \(K+m+R\) inequality constraints.
All coefficients are either input rationals or constants in \(\{-1,0,1\}\). The formulation can therefore be constructed with total binary encoding length polynomial in \(m,\tau,K,R,L\). Keeping the visibility variables avoids expanding and combining the affine coefficients across modes.
The linear program is nonempty: put all mass into sleep, giving \(q=0\), and set \(t=0\). This satisfies the affine inequalities because their minimum at zero is \(F_j(0)=0\), so each affine intercept is nonnegative.
Its feasible region is bounded. Every allocation variable is at most its type’s mass, and every visibility variable is bounded as shown above. For each target, constraint 5 for any one listed affine function bounds \(t_j\) above by a finite constant on the visibility box; constraint 4 bounds it below. Thus the feasible region is a nonempty bounded rational polyhedron.
We apply the standard polynomial-time theorem for rational linear programming: an explicitly encoded rational linear program can be solved in the binary model, returning an exact rational optimum when a finite optimum exists, in time polynomial in its encoding length. See [Khachiyan, *Polynomial algorithms in linear programming*](https://www.mathnet.ru/eng/zvmmf5239). All hypotheses have been verified here.
The exact optimal allocation has polynomial binary encoding length. For completeness, this also follows from the existence of an optimal vertex: after clearing denominators row by row, Cramer’s rule and determinant bounds give polynomial bit lengths for its coordinates. Exact rational output is allowed by the allocation definition, which imposes no integrality restriction.
No step expands the mass into individual sensors. The running time depends on its binary encoding, rather than its numerical magnitude.
The all-sleep allocation has welfare zero, since sleep costs zero and \(F_j(0)=0\). Hence \(V^*\geq0\). Because \(N\geq1\), the returned optimal allocation satisfies
\(\displaystyle W(x)=V^*\geq\frac{V^*}{N}.\)
Thus the requested guarantee holds, including when \(N=1\), where it requires exact optimization.
The proof does not need monotonicity or subadditivity beyond the given promises. The decisive features are continuous allocations and the explicit representation of each valuation as a minimum of rational affine functions.
⟨structured verdict parsed — rendered above⟩
Assessment: proved. The prover resolves the stated mass model by an exact polynomial-time linear programming formulation. The equivalence, encoding-size argument, and approximation guarantee are correct. No major or minor mathematical issues were found.
The argument addresses the actual input model: continuous allocations, explicitly listed modes, rational masses and costs, and explicitly listed affine representations of the valuations. It does not replace the support size with a count of individual sensors.
Writing each valuation as
\[
F_j(u)=\min_{1\leq\ell\leq r_j}\left(b_{j,\ell}+\sum_a d_{j,\ell,a}u_a\right)
\]
is justified by the task. Each list must be nonempty because it represents a finite real-valued function on a nonempty domain. Thus the later use of one listed affine function to bound each value variable is legitimate.
The proof correctly does not impose sign restrictions on the affine slopes: the listed representation suffices for the formulation.
All five families of constraints correctly represent the intended feasible allocations and valuation hypographs.
There is no missing domain constraint or incorrect treatment of simultaneous visibility.
Both directions are valid.
For every feasible allocation, setting \(t_j=F_j(q_j)\) satisfies every affine upper bound and the nonnegativity constraint. The resulting objective equals its welfare.
Conversely, every feasible linear programming point satisfies \(t_j\leq F_j(q_j)\), so its objective is at most the welfare of its allocation component, which is at most \(V^*\).
The maximum defining \(V^*\) exists: the allocation region is nonempty and compact, and a finite minimum of affine functions is continuous. Hence the lifting argument establishes equality of optimal values, rather than merely equality of suprema.
The claim about extracting an optimal allocation also follows: an optimal linear programming point has objective \(V^*\), while its allocation welfare lies between that objective and \(V^*\). Its welfare therefore equals \(V^*\).
The reported counts are correct: \(K+m\tau+m\) variables, \(\tau+m\tau\) equality constraints, and \(K+m+R\) inequality constraints.
The all-sleep point is feasible. In particular, \(F_j(0)=\min_\ell b_{j,\ell}=0\) implies every listed intercept is nonnegative, so \(t_j=0\) satisfies every affine inequality at \(q_j=0\).
The boundedness argument is also correct. Allocation variables and visibility variables are bounded by their respective masses. For each target, any listed affine function has a finite maximum on the visibility box and supplies an upper bound on \(t_j\); its lower bound is zero. The resulting polyhedron is nonempty and bounded.
The construction uses input coefficients and fixed constants. Its dimensions and total binary encoding length are polynomial in the stated parameters. Retaining the visibility variables is a valid way to avoid coefficient expansion.
The invoked theorem is the standard binary-model polynomial-time solvability theorem for explicitly encoded rational linear programs, including recovery of an exact rational optimal solution when an optimum exists. The prover states the needed conclusion and verifies its hypotheses. The [Khachiyan citation](https://www.mathnet.ru/eng/zvmmf5239) identifies the cited publication.
The supplementary optimal-vertex argument is sound: clearing denominators, applying Cramer’s rule, and bounding determinants yields polynomial coordinate bit lengths. These are routine established calculations, not a missing substantive lemma. Neither integrality nor a bound polynomial in the numerical value of the masses is required.
Zero-cost sleep and \(F_j(0)=0\) give \(V^*\geq0\). Together with \(N\geq1\), this validates
\[
W(x)=V^*\geq V^*/N.
\]
This covers both \(V^*=0\) and \(N=1\). Fractional masses and large binary-encoded masses introduce no additional difficulty in the argument.
The proof’s observation that monotonicity and subadditivity are unnecessary is correct: its equivalence uses the explicit minimum-of-affine representation and nonnegativity.
No repair is required. The output establishes exact polynomial-time optimization and consequently the requested approximation guarantee.
⟨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.