Answer: polynomial-time solvable
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximatecan be computed in time O(z · n + n log n), where z is the time taken for a single invocation of hw,b. The proof is omitted due to lack of space. The resulting mechanism for a single facility is given by a feed-forward neural network that takes peaks τ(u1), . . . , τ(un) as inputs and outputs the location of the facility. This architecture, re- ferred to as MoulinNet, is shown in Figure 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational peaks \(\theta_1,\ldots,\theta_\tau\in[0,1]\), rational masses \(\mu\in\Delta_\tau\), and a monotone bounded-complexity mass-indexed phantom function \(a:[0,1]^\tau\to[0,1]\), compute exactly \(F_a(\mu)=\inf_{0\le q\le\mu}\max\{\max_{t:q_t>0}\theta_t,a(q)\}\) and \(\operatorname{SC}(\mu,F_a(\mu))=\sum_t\mu_t|\theta_t-F_a(\mu)|\); for \(K\) facilities, compute all coordinates and the closest-facility social cost.
A society is given by its support: the list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Type \(t\) has a rational peak \(\theta_t\in[0,1]\).
For each of \(K\ge1\) facilities, an explicitly listed phantom function is given by \(a_k(q)=\min_{1\le h\le H_k}\max_{1\le j\le J_{kh}}(b_{khj}+\sum_{t=1}^{\tau}w_{khjt}q_t)\), with positive integer layer sizes, rational coefficients, and \(w_{khjt}\le0\). Inputs promise \(a_k([0,1]^\tau)\subseteq[0,1]\).
Let \(m=\sum_{k,h}J_{kh}\) be the total number of affine forms and \(L\) the total binary input length; state running times in \(m,\tau,L,K\).
Define \(x_k=\inf_{q\in\mathbb R^\tau,\,0\le q_t\le\mu_t}\max\{\max_{t:q_t>0}\theta_t,a_k(q)\}\), with the empty maximum equal to \(0\). Partial masses and \(q=0\) are allowed. The required outputs are all \(x_k\) and \(\operatorname{SC}(\mu,x)=\sum_t\mu_t\min_{1\le k\le K}|\theta_t-x_k|\), exactly; facilities may coincide.
Is exact computation of these facility coordinates and their social cost solvable in polynomial time in \(m,\tau,L,K\), or is it NP-hard?
For finite agent lists, generalized-median evaluation with a coordinatewise nonincreasing min–max affine phantom network takes \(O(zn+n\log n)\) time, where \(z\) is one phantom-network evaluation time ([Golowich, Narasimhan and Parkes](https://www.ijcai.org/Proceedings/2018/0036.pdf)).
No prior result settling this exact mass-indexed evaluation problem was located.
Exact computation is polynomial-time solvable. All facility coordinates and the social cost can be computed using
\(O(m\tau+\tau\log(\tau+1)+K\tau)\) arithmetic operations on integers of \(O(L)\) bits. A conservative bit-complexity bound is
\(O\bigl(L+(m\tau+\tau\log(\tau+1)+K\tau)L^2\bigr)\).
The key fact is that every feasible partial-mass vector is dominated, for this objective, by one of at most \(\tau+1\) full-mass prefix vectors.
Write
\(\ell_{khj}(q)=b_{khj}+\sum_{t=1}^{\tau}w_{khjt}q_t\).
For vectors \(q\le q'\) coordinatewise, the sign condition \(w_{khjt}\le0\) gives
\(\ell_{khj}(q')\le\ell_{khj}(q)\).
Taking the maximum within each layer preserves this inequality, as does taking the minimum over layers. Consequently,
\(a_k(q')\le a_k(q)\)
for every facility \(k\).
Define the objective
\(F_k(q)=\max\{\max_{t:q_t>0}\theta_t,a_k(q)\}\),
using the stipulated empty maximum.
Let \(p_1<\cdots<p_r\) be the distinct peaks occurring in the support, where \(1\le r\le\tau\). Define \(v^{(0)}=0\), and, for \(1\le i\le r\), define
\(v^{(i)}_t=\mu_t\) when \(\theta_t\le p_i\), and \(v^{(i)}_t=0\) otherwise.
These vectors are feasible. Positivity of every support mass implies that the largest peak selected by \(v^{(i)}\) is exactly \(p_i\). Thus
\(F_k(v^{(i)})=\max\{p_i,a_k(v^{(i)})\}\).
Also, the range promise gives
\(F_k(v^{(0)})=a_k(0)\).
Prefix domination lemma. For every feasible \(q\), there is an index \(i\in\{0,\ldots,r\}\) such that
\(F_k(v^{(i)})\le F_k(q)\)
simultaneously for all facilities \(k\).
Proof. If \(q=0\), take \(i=0\). Otherwise, the nonempty finite set of selected types has a largest peak, say
\(p_i=\max_{t:q_t>0}\theta_t\).
When \(\theta_t>p_i\), necessarily \(q_t=0=v^{(i)}_t\). When \(\theta_t\le p_i\), feasibility gives
\(q_t\le\mu_t=v^{(i)}_t\).
Hence \(q\le v^{(i)}\) coordinatewise. Monotonicity yields
\(a_k(v^{(i)})\le a_k(q)\).
Both vectors have largest selected peak \(p_i\), so
\(F_k(v^{(i)})=\max\{p_i,a_k(v^{(i)})\}\le\max\{p_i,a_k(q)\}=F_k(q)\).
This proves the lemma.
It follows that the exact coordinate formula is
\(\displaystyle x_k=\min\left\{ a_k(0),\ \min_{1\le i\le r}\max\{p_i,a_k(v^{(i)})\} \right\}. \)
Indeed, every feasible objective value is at least the minimum on the right by the lemma. Conversely, every candidate on the right is the objective value of a feasible vector.
This also proves that the infimum is attained. Partial masses cannot improve upon the best full-mass prefix. The argument includes tied peaks and peaks equal to zero; the empty vector remains a separate candidate.
Sort the types by peak and group equal peaks. For each affine form, maintain its current value, initially
\(\ell_{khj}(v^{(0)})=b_{khj}\).
Let \(G_i=\{t:\theta_t=p_i\}\). Moving from prefix \(i-1\) to prefix \(i\) updates each affine form by
\(\displaystyle \ell_{khj}(v^{(i)}) = \ell_{khj}(v^{(i-1)}) + \sum_{t\in G_i}w_{khjt}\mu_t. \)
Each type enters once. Updating all affine forms throughout the sweep therefore takes \(O(m\tau)\) arithmetic operations.
At each prefix, compute every layer maximum and facility minimum from the maintained affine values. This takes \(O(m)\) comparisons across all facilities: the number of layers and the number of facilities are each at most \(m\), because all layer sizes are positive. Over at most \(\tau+1\) prefixes, this costs \(O(m\tau)\). Retain the smallest candidate for each facility.
Sorting costs \(O(\tau\log(\tau+1))\) comparisons. Once the coordinates are available, calculate
\(\displaystyle \operatorname{SC}(\mu,x) = \sum_{t=1}^{\tau}\mu_t \min_{1\le k\le K}|\theta_t-x_k| \)
directly in \(O(K\tau)\) arithmetic operations and comparisons. Coincident facilities cause no difficulty.
The total arithmetic-operation count is therefore
\(O(m\tau+\tau\log(\tau+1)+K\tau)\).
To control intermediate bit lengths explicitly, let \(D\) be the product of the positive denominators of all input rationals. Since their total encoding length is at most \(L\), the integer \(D\) has \(O(L)\) bits.
Represent every input rational with denominator \(D\):
\(b_{khj}=B_{khj}/D\),
\(w_{khjt}=W_{khjt}/D\),
\(\mu_t=M_t/D\), and
\(\theta_t=P_t/D\).
All these integer numerators have \(O(L)\) bits.
Maintain affine values with the common denominator \(D^2\). Their numerators are
\(\displaystyle A_{khj}^{(i)} = B_{khj}D+ \sum_{\theta_t\le p_i}W_{khjt}M_t. \)
Thus every update uses integer multiplication and addition. Each product has \(O(L)\) bits, and summing at most \(\tau\) products adds only \(O(\log(\tau+1))\) bits. Since the support is explicitly listed, this is still \(O(L)\).
All network evaluations and coordinate candidates can now be compared as integer numerators over the same denominator \(D^2\). In particular, write the resulting coordinates as \(x_k=X_k/D^2\).
The social cost is represented exactly by
\(\displaystyle \operatorname{SC}(\mu,x) = \frac{ \sum_{t=1}^{\tau} M_t\min_{1\le k\le K}|P_tD-X_k| }{D^3}. \)
Its numerator and denominator also have \(O(L)\) bits. The range promise ensures every coordinate lies in \([0,1]\), so the social cost lies in \([0,1]\). These fractions can optionally be reduced by integer greatest-common-divisor computations.
Constructing \(D\) and converting the input require \(O(m\tau+\tau)\) integer operations, because the coefficients are explicitly listed. Using schoolbook integer arithmetic gives the stated bound
\(\displaystyle O\bigl(L+(m\tau+\tau\log(\tau+1)+K\tau)L^2\bigr). \)
The sorted-prefix principle also appears in the finite-agent evaluation of [Golowich, Narasimhan and Parkes, Theorem 3](https://www.ijcai.org/Proceedings/2018/0036.pdf). The proof above establishes it directly for the specified mass-indexed objective and supplies exact bit-complexity bounds without expanding rational masses into individual agents.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the stated exact computation problem. The prefix domination argument is correct, the algorithm evaluates all necessary candidates, and the claimed arithmetic and bit-complexity bounds hold. No major or minor issues were found.
Positive masses summing to \(1\) imply \(0<\mu_t\le1\). Consequently, every feasible vector lies in \([0,1]^\tau\), where the range promise applies.
For every affine form, \(q\le q'\) and \(w_{khjt}\le0\) imply \(\ell_{khj}(q')\le\ell_{khj}(q)\). Taking maxima over the same nonempty index sets preserves this inequality, and taking minima over the same nonempty layer sets preserves it again. Thus the asserted coordinatewise nonincreasing property of every \(a_k\) follows.
The distinct peaks are well defined because the support is finite and nonempty. Every \(v^{(i)}\) is feasible.
For \(i\ge1\), a supported type has peak \(p_i\), and its positive mass is selected by \(v^{(i)}\). No type with larger peak is selected. Therefore its largest selected peak is exactly \(p_i\), including when \(p_i=0\).
For \(v^{(0)}=0\), the stipulated empty maximum is \(0\). Since \(a_k(0)\ge0\), the equality \(F_k(v^{(0)})=a_k(0)\) is correct.
The proof covers every feasible vector. The zero vector is handled separately. For a nonzero feasible vector, the selected set is finite and nonempty, so its largest peak is one of the \(p_i\).
Every coordinate with peak above \(p_i\) is zero. Every remaining coordinate is at most its full mass. Hence \(q\le v^{(i)}\). Monotonicity decreases the phantom value, while the largest selected peak remains exactly \(p_i\). Taking the maximum of these two quantities yields the claimed inequality.
The selected index depends only on \(q\) and the peaks, so the domination holds simultaneously for all facilities. No continuity assumption or discretization of partial masses is needed.
The two inequalities establishing the formula have the correct directions. Domination shows that every feasible objective value is at least the minimum prefix candidate. Conversely, every prefix candidate is attained by a feasible vector.
Since the candidate set is finite and nonempty, its minimum is attained. Thus replacing the original infimum with this finite minimum is justified. Tied peaks, zero peaks, partial masses, and the empty selection are all covered.
The affine update identity follows directly from the definition of the prefix vectors. The groups partition the support, so each affine form receives exactly one update contribution per type throughout the sweep. This gives \(O(m\tau)\) arithmetic operations.
At each prefix, all layer maxima and facility minima take \(O(m)\) comparisons. Positive layer sizes imply that both the total number of layers and \(K\) are at most \(m\). Candidate comparisons therefore fit within the same bound. There are at most \(\tau+1\) prefixes, and \(\tau\ge1\), giving another \(O(m\tau)\) contribution.
Sorting and grouping take \(O(\tau\log(\tau+1))\) comparisons. Directly computing the nearest-facility distance for each type takes \(O(K\tau)\) operations and comparisons. Coincident facilities do not change this calculation. The stated total operation count is correct.
The product \(D\) of input denominators has bit length bounded by their total encoded length, hence \(O(L)\). Converting each input rational to denominator \(D\) also produces numerators of \(O(L)\) bits: each is an original numerator multiplied by an integer divisor of \(D\).
The maintained affine numerator \(B_{khj}D+\sum_{\theta_t\le p_i}W_{khjt}M_t\) correctly represents the affine value over denominator \(D^2\). Each product has \(O(L)\) bits; summing at most \(\tau\) products adds at most \(O(\log(\tau+1))\) bits. Explicit support encoding ensures this remains \(O(L)\), even when individual affine values fall outside the promised network range.
Peaks can be represented over denominator \(D^2\) using numerators \(P_tD\). Maxima and minima select existing rational values, so the resulting representation \(x_k=X_k/D^2\) is exact.
The displayed social-cost formula follows from subtracting coordinates over denominator \(D^2\) and multiplying by masses over denominator \(D\). Its numerator and denominator have \(O(L)\) bits. No approximate arithmetic is used.
The number of explicitly listed rationals is \(O(m\tau+\tau)\). Constructing \(D\) and converting them require that many integer operations, with all operands of \(O(L)\) bits. Schoolbook multiplication and division cost \(O(L^2)\) per operation; addition and comparison fit within this bound. Including input reading gives the claimed conservative bit complexity.
The final literature comparison is accurate: [Golowich, Narasimhan and Parkes, Theorem 3](https://www.ijcai.org/Proceedings/2018/0036.pdf) states the finite-agent evaluation bound and is preceded by a sorted-prefix formula. The prover uses this only as context; the mass-indexed reduction and complexity bounds are established independently.
No additional clarification or repair 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.