Answer: \(\mathrm P\); exact optimization and threshold decision take \(O((r\tau^4+Tm^2\tau^2)L^2)\) bit operations, where \(m=T+r-1\).
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateOPT NMC-WFCFS(T + r −1, T, 0, 0) com- putes the optimal social cost for the NMC-WFCFS model in O((T +r)2 ×T 2 ×n6 max +T ×n7 max ×r) using dynamic programming.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given stages \(T\) and tolerance \(r\), a finite rational set of arrival-location types \((a,z)\) with rational masses summing to one, choose facility locations \(y_s\) for \(s=1,\ldots,T+r-1\) and service masses \(x_{a,z,s}\) summing to each type's mass, with \(a<a'\) implying every positive service stage for \((a,z)\) is no later than every positive service stage for \((a',z')\), to minimize the total weighted distance sum of \(x_{a,z,s}|y_s-z|\).
Let \(T,r\ge 1\) be integers encoded in unary, and let \(m=T+r-1\) be the number of service stages. A society is given by its support: the list of \(\tau\) distinct types \((a,z)\in\{1,\ldots,T\}\times\mathbb Q\), each with positive mass \(w_{a,z}\) as a binary rational, with \(\sum_{a,z}w_{a,z}=1\). Here \(\tau\) is the support size, not the number of possible types; arrival stages may have no mass. Let \(L\) be the total input bit length.
Choose facility locations \(y_s\in\mathbb R\) and divisible service masses \(x_{a,z,s}\in\mathbb R_{\ge0}\) for \(s\in\{1,\ldots,m\}\), with \(\sum_s x_{a,z,s}=w_{a,z}\) and \(x_{a,z,s}=0\) unless \(a\le s\le a+r-1\).
Impose FCFS: for every pair of support types with \(a<a'\), if \(x_{a,z,s}>0\) and \(x_{a',z',s'}>0\), then \(s\le s'\). Equal arrival stages impose no order, and different arrival stages may share a service stage.
There is one uncapacitated facility per stage, no movement cost, and no restriction on its location. The total cost is \(C=\sum_{a,z}\sum_{s=1}^{m}x_{a,z,s}|y_s-z|\).
Given a binary rational threshold \(B\ge0\), is deciding whether a feasible solution with \(C\le B\) exists in \(\mathrm P\), or is it NP-hard? State running times in \(m,\tau,L,T,r\).
For indivisible unit-weight agents, exact minimum total distance under the same service windows and FCFS condition is computable in time polynomial in the number of agents, \(T\), and \(r\). [Wang et al. (2023)](https://ojs.aaai.org/index.php/AAAI/article/download/25725/25497)
No result settling this exact divisible-mass formulation was located in the literature search.
The decision problem is in \(\mathrm P\). An exact algorithm uses
\(O\!\left((r\tau^4+Tm^2\tau^2)L^2\right)\)
bit operations, where \(m=T+r-1\). In particular, binary rational masses need not be expanded into unit-weight agents.
The proof below gives a dynamic program directly for the stated formulation. The [cited algorithm of Wang et al.](https://ojs.aaai.org/index.php/AAAI/article/download/25725/25497) provides context; its unit-weight result is not needed as a black box.
Write \(\mathcal S\) for the support and \(Q=\{z:(a,z)\in\mathcal S\}\) for the set of distinct spatial coordinates.
Lemma 1. Every feasible divisible solution can be replaced, without increasing cost, by a feasible solution serving each support type entirely at one stage.
Proof. Fix a feasible solution \((x,y)\). For each type \((a,z)\), choose a stage \(s_{a,z}\) minimizing \(|y_s-z|\) among stages with \(x_{a,z,s}>0\). Such a stage exists because its positive mass must be served.
Assign its entire mass to \(s_{a,z}\). Its new cost satisfies
\(w_{a,z}|y_{s_{a,z}}-z|\le\sum_s x_{a,z,s}|y_s-z|\).
The chosen stage belongs to the type’s service window. Moreover, whenever \(a<a'\), both chosen stages had positive mass in the original solution, so the original FCFS condition gives \(s_{a,z}\le s_{a',z'}\). Thus feasibility is preserved. Summing the displayed inequality proves the claim. \(\square\)
Lemma 2. For every fixed assignment of whole support types to stages, optimal facility locations can be chosen from \(Q\).
Proof. At a nonempty stage, aggregate coincident coordinates and write its coordinates as \(z_1<\cdots<z_n\), with positive weights \(v_1,\ldots,v_n\). Let \(V=\sum_jv_j\), and choose the first index \(t\) satisfying \(\sum_{j\le t}v_j\ge V/2\).
For \(F(y)=\sum_jv_j|y-z_j|\), the slope immediately to the left of \(z_t\) is
\(2\sum_{j<t}v_j-V\le0\),
and the slope immediately to its right is
\(2\sum_{j\le t}v_j-V\ge0\).
The slopes are nondecreasing as \(y\) increases, so \(z_t\) minimizes \(F\). It belongs to \(Q\). An empty stage may also be placed anywhere in \(Q\). \(\square\)
There is at least one feasible whole-type assignment: serve each type at its arrival stage. There are finitely many whole-type assignments and facility vectors in \(Q^m\). Lemmas 1–2 therefore show that the original problem has an attained optimum equal to the minimum over this finite family.
Henceforth we optimize whole-type assignments with facility locations in \(Q\).
Consider one arrival cohort, whose support coordinates are \(z_1<\cdots<z_n\), with weights \(w_1,\ldots,w_n\).
For \(1\le i\le j\le n\), define the optimal cost of serving that block with one free facility:
\(g(i,j)=\min_y\sum_{t=i}^jw_t|z_t-y|\).
For a prescribed facility position \(f\), define
\(g_f(i,j)=\sum_{t=i}^jw_t|z_t-f|\).
By Lemma 2, \(g(i,j)\) is attained at a weighted median of the block.
Let \(F=(f_1,\ldots,f_d)\), where \(d\le2\), be a list of fixed centers. Define \(H(k,F)\) as the minimum cost of serving the cohort using these fixed centers and at most \(k\) additional free centers. Centers may be unused.
Lemma 3. All values \(H(k,F)\), for \(0\le k\le r-1\), can be computed in \(O(rn^2)\) arithmetic operations once the block costs are available.
Proof. For any finite collection of centers, assign each coordinate to a nearest center, resolving ties toward the smaller center coordinate. Coincident centers can be represented by one label, because using every center is not required.
The resulting nonempty assignment blocks are consecutive in spatial order. Indeed, for two centers \(u<v\),
\(|z-u|\le|z-v|\quad\Longleftrightarrow\quad z\le(u+v)/2\).
Thus a nearest-center choice cannot move from a larger center to a smaller center as \(z\) increases.
We can consequently optimize over partitions into consecutive blocks. Let \(E(j,h,M)\) be the minimum cost of partitioning the first \(j\) coordinates into nonempty consecutive blocks, using exactly \(h\) free-center blocks and exactly the fixed-center labels in \(M\subseteq\{1,\ldots,d\}\), each once.
Initialize \(E(0,0,\varnothing)=0\), and set all other states with \(j=0\) to infinity. For \(j>0\), enumerate the start \(i+1\) of the final block, where \(0\le i<j\). Its possible contributions are:
Take the minimum of these candidates. Then
\(H(k,F)=\min_{0\le h\le k,\ M\subseteq\{1,\ldots,d\}}E(n,h,M)\).
To verify equality, first observe that every DP partition gives a valid assignment to at most \(k\) free centers and the prescribed fixed centers: place each free center at its block’s weighted median. Therefore \(H(k,F)\) is at most the DP value.
Conversely, an optimum for \(H(k,F)\) exists: for each assignment to center labels, every nonempty free center can be placed at a weighted median, leaving finitely many relevant possibilities. Assigning to nearest centers produces consecutive blocks. These blocks occur among the DP candidates, and replacing each free center by its block’s weighted median cannot increase cost. Therefore the DP value is at most \(H(k,F)\).
There are \(O(rn)\) states because \(d\le2\), and each state considers \(O(n)\) candidates. \(\square\)
List only the nonempty arrival stages:
\(a_1<a_2<\cdots<a_K\),
and let \(n_i\) be the support size of cohort \(i\). Thus
\(K\le T,\qquad \sum_{i=1}^K n_i=\tau\).
Their actual arrival stages remain \(a_i\); empty arrival stages are not compressed out of service windows.
For any feasible whole-type schedule, let \(b_i\) be the latest stage serving cohort \(i\), and set \(b_0=0\). FCFS gives
\(b_{i-1}\le s\le b_i\)
for every stage \(s\) serving cohort \(i\). Also \(a_i\le b_i\le a_i+r-1\).
This yields the central observation: when processing the next cohort, the only previously chosen facility that it can use is the one at the previous boundary stage \(b_{i-1}\). Earlier facilities cannot be used. Facilities strictly between consecutive boundaries serve only the current cohort.
The algorithm also permits a boundary stage to be unused by the current cohort. This only reserves that stage and restricts subsequent cohorts to stages at least as large. Such reservations remain feasible.
A state \((b,p)\) records a reserved boundary stage \(b\) and its facility position \(p\in Q\). All processed cohorts have been served by stage \(b\), and subsequent cohorts will be assigned only to stages at least \(b\).
Start with the sentinel state \(D_0(0,\bot)=0\).
When processing cohort \(i\), write \(a=a_i\). From a previous state \((b,p)\), choose its new boundary
\(c\in\{a,\ldots,a+r-1\},\qquad c\ge b\),
and a boundary facility position \(q\in Q\).
There are two transition cases.
If \(c=b\), all of the current cohort must be served at that stage. Its facility remains \(p\), so \(q=p\), and the added cost is
\(\sum_{t=1}^{n_i}w_t|z_t-p|\).
If \(c>b\), stage \(c\) receives the prescribed facility \(q\).
The available intermediate stages are precisely
\(\{s:\max\{a,b+1\}\le s<c\}\).
Their number is
\(k=c-\max\{a,b+1\}\),
which satisfies \(0\le k\le r-1\).
If \(b\ge a\), the previous boundary facility \(p\) is also inside the current cohort’s window. Otherwise it cannot be used. Consequently the added cost is
\(H_i(k,(p,q))\quad\text{if }b\ge a\),
and
\(H_i(k,(q))\quad\text{if }b<a\).
Here \(H_i\) is the clustering subproblem for cohort \(i\). Its free centers can be assigned injectively to the \(k\) intermediate stages. This is valid because equal arrival stages impose no service order.
For each transition, update \(D_i(c,q)\) with the previous value plus the indicated added cost, taking the minimum over all predecessors.
The output is
\(C_{\mathrm{DP}}=\min_{c,q}D_K(c,q)\).
Proposition. \(C_{\mathrm{DP}}\) equals the optimum of the original divisible problem.
Proof: every DP path is feasible. Proceed inductively. Before a transition from \((b,p)\), all previously processed mass is served at stages at most \(b\).
If \(c=b\), the current cohort is served at \(b\), within its window.
If \(c>b\), the clustering solution uses only the eligible old boundary stage, eligible intermediate stages, and stage \(c\). Each is within the current cohort’s window. Previously used facilities are preserved, and the intermediate stages and stage \(c\) contain no previously served mass.
In both cases, every current service stage is at least \(b\). Every earlier service stage is at most \(b\), so FCFS holds between the current cohort and every earlier cohort. Stage sharing causes no difficulty because equality is allowed.
The block DP supplies actual whole-type assignments realizing each added cost. Thus every finite outer DP path gives a feasible solution of that cost, and
\(C_{\mathrm{DP}}\ge C^\star\),
where \(C^\star\) is the original optimum.
Proof: an optimal schedule is represented. By Section 1, choose an optimal whole-type schedule with facility positions in \(Q\). For each cohort, use its actual latest service stage as \(b_i\), and its facility position there as the corresponding boundary position.
FCFS gives \(b_{i-1}\le b_i\) and places every service stage of cohort \(i\) between these boundaries.
If the boundaries coincide, the same-boundary transition reproduces its cost.
If they differ, all facilities used by this cohort belong to exactly the set allowed by the advancing-boundary transition: the previous boundary if eligible, the new boundary, and eligible intermediate stages. Hence its assignment is a feasible candidate for that transition’s clustering subproblem. The transition cost is at most the cohort’s cost in the optimal schedule.
Following these boundaries through the DP gives
\(C_{\mathrm{DP}}\le C^\star\).
Together, the two inequalities prove equality. \(\square\)
Put \(q=|Q|\le\tau\).
For each cohort, all free block costs \(g(i,j)\) can be computed in \(O(n_i^3)\) arithmetic operations: scan each block to find a weighted median and evaluate its cost. Fixed-center block costs can be obtained from prefix sums for each \(f\in Q\).
There are \(O(q^2)\) relevant fixed-center lists of length one or two. Lemma 3 computes their tables for all \(0\le k\le r-1\) in
\(O(rq^2n_i^2)\)
arithmetic operations per cohort.
The outer DP has \(O(mq)\) states per cohort and at most \(O(mq)\) transitions per state. Therefore the total number of arithmetic operations is
\(O\!\left(\tau^3+rq^2\sum_i n_i^2+Km^2q^2\right)\).
Using \(\sum_i n_i^2\le\tau^2\), \(q\le\tau\), and \(K\le T\), this is at most
\(O(r\tau^4+Tm^2\tau^2)\).
It remains to bound the arithmetic bit lengths. Let \(W\) be the product of the input mass denominators, and \(Z\) the product of the input coordinate denominators. Write
\(w_{a,z}=u_{a,z}/W,\qquad z=v_z/Z\),
with integer \(u_{a,z}>0\) and integer \(v_z\). Both products and all these integers have \(O(L)\) bits. Moreover, \(\sum_{a,z}u_{a,z}=W\).
Measure cost in units of \(1/(WZ)\). Every contribution becomes the integer
\(u_{a,z}|v_y-v_z|\).
Let \(R=\max_{z\in Q}v_z-\min_{z\in Q}v_z\). Since all chosen centers lie in \(Q\), every finite cost stored by either DP is at most \(WR\), and therefore has \(O(L)\) bits. Intermediate prefix sums also have \(O(L)\) bits.
Using elementary integer arithmetic, each required operation costs at most \(O(L^2)\) bit operations. Finally, compare the optimum \(A/(WZ)\) with the binary rational threshold by cross multiplication.
The resulting bound is
\(O\!\left((r\tau^4+Tm^2\tau^2)L^2\right) =O\!\left((r\tau^4+T(T+r-1)^2\tau^2)L^2\right)\).
Because \(T\) and \(r\) are unary encoded, this is polynomial in the total input length.
As an additional check, implementations of these recurrences agreed with exhaustive feasible-assignment enumeration on 350 small weighted instances, including empty arrival stages. The clustering recurrence also agreed with exhaustive free-center enumeration on 150 subproblems, including coincident fixed centers. The correctness proof above is independent of these checks.
⟨structured verdict parsed — rendered above⟩
The argument establishes that the decision problem is in \(\mathrm P\), with the stated bit complexity. I found no mathematical errors or gaps requiring repair.
Lemma 1 is correct. Every support type has positive mass, so at least one stage receives positive service mass from it. Choosing a cheapest stage among those stages gives
\[
w_{a,z}|y_{s_{a,z}}-z|
\le
\sum_s x_{a,z,s}|y_s-z|.
\]
Both feasibility conditions survive this change:
The simultaneous reassignment of all types does not introduce any new pair of occupied stages beyond those already covered by the original FCFS condition. Equal arrival stages require no additional check.
Lemma 2 is correct. The displayed left and right slopes at the chosen weighted median have the required signs. Since the slopes of the weighted absolute-distance objective are nondecreasing, that coordinate is a global minimizer. This includes the case of equality at half the total weight, where the minimizer need not be unique.
The support is nonempty because its positive masses sum to one. Thus \(Q\) is nonempty, and placing empty-stage facilities in \(Q\) is legitimate.
The finite-family argument also correctly establishes attainment: every divisible solution has a whole-type replacement of no greater cost, and every whole-type assignment has an optimal facility vector in \(Q^m\). Consequently, the original optimum equals the minimum over the stated finite family.
Lemma 3 is correct.
For distinct centers \(u<v\), the stated comparison
\[
|z-u|\le |z-v|
\quad\Longleftrightarrow\quad
z\le (u+v)/2
\]
is valid. Resolving ties toward the smaller coordinate therefore makes nearest-center assignments consecutive in spatial order.
Coincident centers do not cause a problem: one representative label suffices because neither fixed nor free centers are required to be used.
The state \(E(j,h,M)\) and its recurrence correctly enumerate consecutive partitions:
The two inequalities establishing equality with \(H(k,F)\) are sound. Every finite recurrence candidate gives an actual assignment to the permitted centers. Conversely, a clustering optimum can be assigned to nearest centers, producing consecutive blocks; replacing each used free center by its block’s weighted median cannot increase cost.
The recurrence does not require fixed-center labels to appear in coordinate order. This is harmless: any partition it considers still gives a valid assignment, and the nearest-center partition needed for the converse is among its candidates.
With at most two fixed labels, the subset factor is constant. There are \(O(rn)\) states and \(O(n)\) final-block choices per state, giving the claimed \(O(rn^2)\) arithmetic operations.
The boundary observation is valid.
For a nonempty cohort \(i\), its actual latest service stage \(b_i\) exists. FCFS implies that every stage serving cohort \(i\) is at least \(b_{i-1}\), while the definition of \(b_i\) supplies the upper bound.
Thus:
Keeping the actual arrival stages \(a_i\) preserves service windows when some arrival stages are empty.
The extension to reserved, possibly unused boundary stages is also valid. It restricts future assignments but does not violate feasibility. Completeness is supplied separately by following actual boundaries of an optimum, so these additional restrictions on other paths do not exclude every optimum.
Both transition cases are correct.
When \(c=b\), the current cohort can use only that stage. Since \(c\) is chosen from its service window, this assignment is eligible. Requiring \(q=p\) correctly preserves the existing facility.
When \(c>b\), the available new intermediate stages are exactly
\[
\max\{a,b+1\},\ldots,c-1.
\]
Their number is
\[
k=c-\max\{a,b+1\}.
\]
The range is correct: \(c\ge a\) and \(c>b\) imply \(k\ge0\), while \(c\le a+r-1\) implies \(k\le r-1\).
The previous boundary is eligible precisely when \(b\ge a\); its upper-window eligibility follows from \(b<c\le a+r-1\). Stage \(c\) is eligible by construction.
Assigning free centers injectively to intermediate stages is valid because there is no order constraint within one arrival cohort.
The sentinel transition is covered: initially \(b=0<a\), so the first transition advances and uses only the new fixed center and eligible intermediate stages. It never accesses the undefined sentinel facility position.
Both directions of the proposition hold.
Feasibility of DP paths. Earlier service occurs at stages at most \(b\); current service occurs at stages at least \(b\). This verifies FCFS against every earlier cohort. Advancing transitions introduce facilities only at previously unused stages and preserve the existing boundary facility. The clustering recurrence realizes the stated costs with actual whole-type assignments.
Therefore,
\[
C_{\mathrm{DP}}\ge C^\star.
\]
Representation of an optimum. Section 1 supplies an attained optimal whole-type schedule with locations in \(Q\). Its actual cohort boundaries and boundary locations form permitted outer states. For each advancing transition, the optimum’s cohort assignment is a feasible candidate for the corresponding clustering subproblem. For coincident boundaries, the same-boundary transition reproduces its cost.
Therefore,
\[
C_{\mathrm{DP}}\le C^\star.
\]
The equality and the reduction to threshold decision follow.
The operation counts are consistent:
Using \(q\le\tau\), \(K\le T\), and \(\sum_i n_i^2\le\tau^2\), the total is bounded by
\[
O(r\tau^4+Tm^2\tau^2).
\]
The block-cost and fixed-center preprocessing costs are absorbed by this bound.
The common-denominator argument is valid. Products of input denominators and the resulting scaled numerators have \(O(L)\) bits. Every assigned coordinate and every chosen center lies in \(Q\), so the scaled distance is at most \(R\). Every finite partition or outer-DP cost serves each included type once, giving the bound \(WR\).
This bound applies to finite recurrence values and candidate sums; infeasible states can use a separate infinity marker. Negative coordinates do not affect the bit-length conclusion.
Elementary integer arithmetic therefore supplies the claimed \(O(L^2)\) cost per operation. Cross multiplication against the rational threshold also uses integers of \(O(L)\) bits.
The resulting bound is
\[
O\!\left((r\tau^4+Tm^2\tau^2)L^2\right)
=
O\!\left((r\tau^4+T(T+r-1)^2\tau^2)L^2\right).
\]
Unary encoding of \(T\) and \(r\) makes this polynomial in total input length.
The reported exhaustive checks cannot be independently reproduced from the supplied output because no implementation or instance data is included. They are explicitly supplementary, and the proof does not depend on them. Their absence creates no gap in the mathematical conclusion.
No proof repair or additional mathematical 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.