Answer: Polynomial-time solvable in \(\tau,k,L\), with exact cost and optimal locations computable in \(O(\tau^2L^2+\min\{k,\tau\}\tau^2L+kL)\) bit operations.
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet x be the reports of n agents. Let y be the solution to the k-FLP, i.e. the facility locations that minimize the Social Cost. Then the set {yj}j∈[k] is the support of a measure ν(k,n) that solves problem (5). Moreover, we have that SCopt(x) = W1(µx, ν(k,n)) = min λ∈Pk(R) W1(µx, λ).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(k\) and a finite distribution \(\mu=\sum_{i=1}^{\tau}\mu_i\delta_{a_i}\) with ordered rational locations \(a_i\), positive rational masses \(\mu_i\), and \(\sum_i\mu_i=1\), compute facility locations \(y_1,\ldots,y_k\in\mathbb{R}\) minimizing \(\sum_{i=1}^{\tau}\mu_i\min_{j\in[k]}|a_i-y_j|\), together with the minimum cost.
A society is given by its support: \(\mu=\sum_{i=1}^{\tau}\mu_i\delta_{a_i}\), with \(a_1<\cdots<a_{\tau}\) rational, positive binary-rational masses \(\mu_i\), and \(\sum_i\mu_i=1\). Here \(\tau\geq1\) is the support size, not the number of possible types.
Given a positive integer \(k\), compute facility locations \(y_1,\ldots,y_k\in\mathbb R\) minimizing \(C_\mu(y)=\sum_{i=1}^{\tau}\mu_i\min_{1\leq j\leq k}|a_i-y_j|\), together with the exact minimum cost. Repeated facility locations are allowed; any minimizer is acceptable, and distance ties do not affect the objective.
Let \(L\) be the total binary input length. State running times in \(\tau,k,L\); the ambient dimension is fixed at \(m=1\).
Is this exact facility-location problem solvable in polynomial time in \(\tau,k,L\), or is it NP-hard?
For equally weighted finite societies, optimal facility location is equivalent to Wasserstein projection onto probability measures with at most \(k\) support points; this is an equivalence result, not a complexity classification.
[Verified weighted line-median algorithms](https://cse.hkust.edu.hk/faculty/golin/pubs/Algorithmica_KMedian_On_Line.pdf) compute optimal costs and placements in polynomial time. Their support-restricted formulation has the same optimum as unrestricted facility placement on a line; consequently, the supplied finite-support problem is already tractable, rather than an open complexity target.
The problem is polynomial-time solvable in \(\tau,k,L\). Let \(h=\min\{k,\tau\}\). A direct dynamic program computes an optimal placement and the exact minimum cost using
\(O(h\tau^2+k)\)
arithmetic operations. With ordinary binary encodings of rational numbers, the algorithm below has the bit-time bound
\(O(\tau^2L^2+h\tau^2L+kL)\).
The \(kL\) term accounts for explicitly outputting \(k\) rational locations. The proof applies to the given weights directly, without expanding masses into equally weighted individuals.
For \(1\leq \ell\leq u\leq\tau\), define
\(H(\ell,u)=\min_{z\in\mathbb R}\sum_{i=\ell}^{u}\mu_i|a_i-z|\).
Write \(M=\sum_{i=\ell}^{u}\mu_i\), and let \(r\) be the smallest index satisfying
\(\displaystyle \sum_{i=\ell}^{r}\mu_i\geq \frac{M}{2}\).
Then \(a_r\) attains the minimum defining \(H(\ell,u)\).
To prove this, set \(F(z)=\sum_{i=\ell}^{u}\mu_i|a_i-z|\). If \(z\geq a_r\), every point with index at most \(r\) contributes exactly \(\mu_i(z-a_r)\) to \(F(z)-F(a_r)\). For every other point, the triangle inequality gives a contribution at least \(-\mu_i(z-a_r)\). Consequently,
\(\displaystyle F(z)-F(a_r)\geq \left(2\sum_{i=\ell}^{r}\mu_i-M\right)(z-a_r)\geq0.\)
If \(z\leq a_r\), the analogous argument gives
\(\displaystyle F(z)-F(a_r)\geq \left(2\sum_{i=r}^{u}\mu_i-M\right)(a_r-z)\geq0.\)
The last inequality holds because the minimality of \(r\) implies \(\sum_{i=\ell}^{r-1}\mu_i<M/2\), so \(\sum_{i=r}^{u}\mu_i>M/2\).
Thus
\(\displaystyle H(\ell,u)=\sum_{i=\ell}^{u}\mu_i|a_i-a_r|.\)
In particular, an optimal facility for each block can be chosen from the input support.
Take any \(k\)-tuple of real facility locations. Remove duplicates and sort the remaining locations as \(c_1<\cdots<c_q\), where \(q\leq k\). Assign each support point to a nearest facility, breaking ties consistently.
The assigned facility indices are nondecreasing along the support. Indeed, suppose \(a_i<a_j\), but \(a_i\) is assigned to \(c_p\) and \(a_j\) to \(c_s\), with \(p>s\). Their nearest-facility inequalities imply
\(\displaystyle |a_i-c_p|\leq|a_i-c_s|\quad\Longrightarrow\quad a_i\geq\frac{c_s+c_p}{2},\)
and
\(\displaystyle |a_j-c_s|\leq|a_j-c_p|\quad\Longrightarrow\quad a_j\leq\frac{c_s+c_p}{2}.\)
These conclusions contradict \(a_i<a_j\).
After discarding facilities assigned no support points, the assignment therefore partitions the support into at most \(h\) nonempty consecutive blocks.
Let \(P\) be the minimum, over all such partitions, of the sum of their block costs \(H\). There are finitely many partitions, so this minimum exists.
For every real placement \(y\), its nearest-facility partition satisfies
\(\displaystyle P\leq \sum_{\text{assigned blocks }[\ell,u]}H(\ell,u)\leq C_\mu(y).\)
Conversely, choose a partition attaining \(P\), place one facility at a weighted median of each block, and repeat any chosen location until there are exactly \(k\) facilities. Each point can use its block’s facility, hence this placement satisfies \(C_\mu(y)\leq P\). Applying the preceding inequality to this same placement gives equality.
Therefore the unrestricted optimum equals \(P\), and some optimum uses only input support locations. This also establishes existence of a minimizer.
Let \(D(t,j)\) be the minimum sum of block costs for a partition of \(a_1,\ldots,a_j\) into exactly \(t\) nonempty consecutive blocks. Set
\(D(0,0)=0,\qquad D(0,j)=+\infty\text{ for }j>0,\qquad D(t,j)=+\infty\text{ for }j<t.\)
For \(1\leq t\leq h\) and \(t\leq j\leq\tau\), use the recurrence
\(\displaystyle D(t,j)=\min_{t-1\leq s<j}\bigl(D(t-1,s)+H(s+1,j)\bigr).\)
Every partition counted by \(D(t,j)\) has a unique final block \([s+1,j]\); its preceding blocks partition the first \(s\) points. Conversely, any feasible preceding partition followed by this final block is feasible. These two observations prove the recurrence.
By Section 2, the exact optimal cost is
\(\displaystyle \operatorname{OPT}=\min_{1\leq t\leq h}D(t,\tau).\)
Store a minimizing predecessor \(s\) at every finite table entry. Choose a minimizing terminal value, trace its predecessors to recover the blocks, and output their weighted medians. Pad the resulting list with repetitions to obtain exactly \(k\) locations.
If \(k\geq\tau\), the simpler solution places a facility at every \(a_i\), pads with repetitions, and has exact cost \(0\).
Use the usual binary encoding of each rational by its integer numerator and positive integer denominator. Write
\(a_i=p_i/q_i,\qquad \mu_i=b_i/d_i,\qquad q_i,d_i>0.\)
Define common denominators and scaled integers by
\(\displaystyle Q=\prod_{i=1}^{\tau}q_i,\qquad B=\prod_{i=1}^{\tau}d_i,\qquad A_i=Qa_i,\qquad w_i=B\mu_i.\)
Then the \(A_i\) are strictly increasing integers, the \(w_i\) are positive integers, and \(\sum_iw_i=B\). Every scaled cost satisfies
\(\displaystyle \sum_i\mu_i|a_i-a_r|=\frac{1}{BQ}\sum_iw_i|A_i-A_r|.\)
Thus all comparisons and optimization can use integers.
Define prefix sums
\(\displaystyle W_j=\sum_{i=1}^{j}w_i,\qquad T_j=\sum_{i=1}^{j}w_iA_i,\qquad W_0=T_0=0.\)
For a block \([\ell,u]\), its median index is the smallest \(r\) satisfying
\(2(W_r-W_{\ell-1})\geq W_u-W_{\ell-1}.\)
Its integer cost is
\(\displaystyle G(\ell,u)=A_r(W_r-W_{\ell-1})-(T_r-T_{\ell-1})+(T_u-T_r)-A_r(W_u-W_r).\)
The first two terms sum \(w_i(A_r-A_i)\) over indices at most \(r\); the last two sum \(w_i(A_i-A_r)\) over indices greater than \(r\). Therefore \(H(\ell,u)=G(\ell,u)/(BQ)\).
For each fixed \(\ell\), the threshold \((W_u+W_{\ell-1})/2\) increases as \(u\) increases. Hence the median index never decreases. A forward scan finds all median indices for this \(\ell\) in \(O(\tau)\) operations. The prefix-sum formula then evaluates each block cost in constant arithmetic time. All block costs and median indices take \(O(\tau^2)\) arithmetic operations.
Run the dynamic program on the integers \(G\). It has \(O(h\tau)\) entries and at most \(\tau\) candidates per entry, giving \(O(h\tau^2)\) integer additions and comparisons. If its optimal integer value is \(V\), return the exact rational cost \(V/(BQ)\); reduction of this fraction is unnecessary.
To verify the bit bound:
This proves the claimed polynomial running time. Working storage, excluding the output list, is \(O((\tau^2+h\tau)L)\) bits.
The supplied paper defines its line problem with arbitrary nonnegative weights and support-restricted facilities. Setting its startup costs to zero gives the present support-restricted problem; it also provides dynamic programming and placement reconstruction. Section 2 above proves the required equivalence with unrestricted placement. See [Fleischer, Golin, and Zhang, *Online Maintenance of k-Medians and k-Covers on a Line*](https://cse.hkust.edu.hk/faculty/golin/pubs/Algorithmica_KMedian_On_Line.pdf).
If \(k\) is binary-encoded, it can be exponentially large in \(L\). Explicitly listing \(k\) locations then necessarily takes at least \(\Omega(k)\) output time. The optimal cost and a representation consisting of at most \(\tau\) locations plus a repetition count are computable in polynomial time in \(L\). The requested explicit output is computable in polynomial time in \(\tau,k,L\).
Thus the target problem is tractable; its Wasserstein interpretation is not needed for the complexity classification.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The argument establishes an optimal unrestricted placement, gives an exact algorithm for arbitrary positive rational masses, and justifies polynomial running time in \(\tau,k,L\). No major or minor mathematical issues were found.
The distinction between explicit output of \(k\) locations and a compact representation when \(k\) is binary encoded is also handled correctly.
The median index exists because the block is nonempty and its masses are positive.
For \(z\geq a_r\), the contributions from indices at most \(r\) are exactly as stated. The lower bound for all other contributions follows from the triangle inequality. The resulting coefficient is nonnegative by the defining inequality for \(r\).
For \(z\leq a_r\), the symmetric estimate is correct. Minimality of \(r\) gives
\[
\sum_{i=\ell}^{r-1}\mu_i<M/2,
\]
including \(r=\ell\), where the sum is empty. Thus the mass at indices at least \(r\) exceeds half the block mass.
The argument covers negative coordinates, singleton blocks, and the case where a prefix has exactly half the block mass. Uniqueness is unnecessary: the chosen support point is a valid minimizer.
Assessment: Correct and complete.
Removing duplicates preserves the objective. Since \(k\geq1\), at least one distinct facility remains.
The two nearest-facility implications used to rule out an inversion are valid for \(c_s<c_p\). They force
\[
a_i\geq(c_s+c_p)/2\geq a_j,
\]
contradicting \(a_i<a_j\). This argument remains valid with distance ties.
Consequently, the nonempty assignment classes are consecutive blocks. Their number is at most both \(k\) and \(\tau\), hence at most \(h\).
Both comparisons with \(P\) are justified:
Applying the first comparison to the constructed placement establishes equality. Padding with repeated locations preserves the objective.
This proves both existence of an unrestricted minimizer and equality with the support-restricted optimum.
Assessment: Correct and complete.
The state definition uses exactly \(t\) nonempty blocks. The initialization correctly handles the empty prefix and infeasible states.
The recurrence’s range \(t-1\leq s<j\) ensures that the preceding prefix can contain \(t-1\) nonempty blocks and that the final block is nonempty. Infeasible predecessors contribute \(+\infty\). For \(t=1\), only the predecessor \(D(0,0)\) is finite.
The final-block decomposition establishes the recurrence in both directions. Minimizing over \(1\leq t\leq h\) matches the partition problem established in Section 2.
Stored predecessors suffice to reconstruct a minimizing partition. Its median indices suffice to output the locations. The separate \(k\geq\tau\) case correctly returns zero cost, since all support points receive facilities and the objective is nonnegative.
Assessment: Correct and complete.
The products \(Q\) and \(B\) are valid common denominators. Thus \(A_i\) and \(w_i\) are integers, their stated order and positivity properties hold, and normalization gives \(\sum_iw_i=B\).
The scaled-cost identity is correct. The median comparison using \(W\) is exactly the original weighted-median condition after multiplication by \(B\).
Expanding the prefix-sum expression for \(G(\ell,u)\) confirms both signs and both index ranges. The median’s own contribution is zero, so its inclusion in the left sum causes no error.
For fixed \(\ell\), the median threshold increases with \(u\). Since cumulative weights increase strictly, the first qualifying index cannot decrease. A forward scan therefore takes \(O(\tau)\) operations for each left endpoint.
Running the dynamic program on \(G\) preserves all comparisons and minimizing choices because every cost has the same positive denominator \(BQ\).
Assessment: Correct and complete.
The claimed bounds hold under the stated ordinary numerator-and-denominator binary encoding.
The denominator products have \(O(L)\) bits because their factor bit lengths sum to at most the input length. The scaled coordinates and weights likewise have \(O(L)\) bits.
The prefix-sum estimate
\[
|T_j|\leq B\max_i|A_i|
\]
is valid even when coordinates are negative. Block costs and finite dynamic-programming candidates are nonnegative and bounded by \(B(A_\tau-A_1)\): each candidate represents a partition of a prefix into disjoint blocks.
Thus elementary multiplication and division operate on \(O(L)\)-bit integers, while dynamic-programming additions and comparisons cost \(O(L)\) each. The preprocessing bound \(O(\tau^2L^2)\) is conservative but valid. Reconstruction and explicit output fit the stated bounds.
The storage bound also accounts for predecessor and median indices, whose bit lengths are bounded by \(O(L)\). The symbol \(+\infty\) can be stored as a flag rather than an integer.
Assessment: The arithmetic-operation, bit-time, and storage bounds are justified.
The cited paper’s Figure 1 permits nonnegative weights and startup costs and restricts facilities to input points. Its Section 2.1 supplies dynamic programming and placement reconstruction. The prover’s description is accurate. [Fleischer, Golin, and Zhang, *Online Maintenance of k-Medians and k-Covers on a Line*](https://cse.hkust.edu.hk/faculty/golin/pubs/Algorithmica_KMedian_On_Line.pdf).
The complexity conclusion does not depend on an unstated external theorem: Sections 1–4 independently establish the required algorithm.
The binary encoding qualification is correct. Explicitly listing \(k\) locations requires output time proportional to \(k\), while a list of at most \(\tau\) locations with a repetition count has polynomial size in \(L\). This is consistent with the task’s requested polynomial bound in \(\tau,k,L\).
No mathematical 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.