Answer: The decision problem is in \(\mathrm{P}\), with running time \(\bigl(T(\tau+1)(k+T\tau)+L\bigr)^{O(1)}\) bit operations.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a mechanism that computes the optimal solution to a gener- alised facility reallocation problem in time O(T 2(2 max{Tn, k})k+1). As mentioned in Section 1.1, the paper [11] provides a strongly related and impor- tant result for the special case of this problem where all weights are equal: In this case, the authors show that there exists an algorithm that is not only polynomial in T and n, but also polynomial in k. Their algorithm can be generalised to handle the case where the objective is a weighted sum of the total movement cost and the total distance of the agents to the facility.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(T\), \(k\), fixed starting locations \(y^0\in\mathbb{Q}^k\), total mass \(N>0\), and a rational distribution \(\mu\) over \(\tau\) types \(\theta=(w_\theta,x^\theta_1,\ldots,x^\theta_T)\), choose facility locations \(y^1,\ldots,y^T\in\mathbb{R}^k\) minimizing \(\sum_{t=1}^T\left(N\sum_{\theta=1}^{\tau}\mu_\theta w_\theta\min_{j\in[k]}|x^\theta_t-y^t_j|+\sum_{j=1}^k|y^t_j-y^{t-1}_j|\right)\).
An offline facility reallocation instance has \(T,k\geq1\), starting locations \(y^0\in\mathbb{Q}^k\), and total mass \(N\in\mathbb{Q}_{>0}\). A society is given by its support: the list of its \(\tau\geq1\) positive-mass types \(\theta=(w_\theta,x^\theta_1,\ldots,x^\theta_T)\), with \(w_\theta\in\mathbb{Q}_{\geq0}\), \(x^\theta_t\in\mathbb{Q}\), and binary-rational probabilities \(\mu_\theta>0\) summing to \(1\); type \(\theta\) has mass \(N\mu_\theta\). Here \(\tau\) is the support size, not the number of possible types.
Choose \(y^1,\ldots,y^T\in\mathbb{R}^k\) to minimize \(C(y)=\sum_{t=1}^T\left(N\sum_{\theta=1}^{\tau}\mu_\theta w_\theta\min_{1\leq j\leq k}|x^\theta_t-y^t_j|+\sum_{j=1}^k|y^t_j-y^{t-1}_j|\right)\). Facilities retain their labels for movement costs, may coincide, and have no capacity constraints; nearest-facility ties do not affect costs.
For the decision version, an additional binary-rational threshold \(B\geq0\) is given, and the question is whether some placement satisfies \(C(y)\leq B\). Let \(L\) be the total input bit length; state running times in \(T,k,\tau,L\) (the spatial dimension is \(m=1\)).
Is this decision problem in \(\mathrm{P}\), with running time polynomial in \(T,k,\tau,L\), or is it \(\mathrm{NP}\)-hard when \(k\) is part of the input?
For finite weighted societies with \(n\) agents, an exact algorithm uses \(O(T^2(2\max\{Tn,k\})^{k+1})\) arithmetic operations, giving an XP bound in \(k\). [Source](https://link.springer.com/article/10.1007/s00453-022-00993-1)
The unweighted finite problem has an exact algorithm polynomial in \(n,T,k\). [Source](https://www.ijcai.org/proceedings/2019/0039.pdf)
The literature search located neither hardness for the weighted problem on the line nor a result explicitly settling the binary-rational mass formulation above.
The decision problem is in \(\mathrm{P}\), including when \(\,k\,\) is part of the input. An exact algorithm uses
\[ \bigl(T(\tau+1)(k+T\tau)+L\bigr)^{O(1)} \]
bit operations.
The proof uses fractional facility placements and a common quantile offset, following the rounding idea in [the cited IJCAI paper](https://www.ijcai.org/proceedings/2019/0039.pdf). Crucially, we prove the service-cost bound separately for every type. This establishes its validity for arbitrary nonnegative rational weights.
Define \(\,a_\theta=N\mu_\theta w_\theta\geq0\,\). These coefficients have bit length \(\,O(L)\,\), and the objective becomes
\[ C(y)=\sum_{t=1}^{T}\left( \sum_{\theta=1}^{\tau}a_\theta\min_j|x_t^\theta-y_j^t| +\sum_{j=1}^{k}|y_j^t-y_j^{t-1}| \right). \]
Let
\[ S=\{y_j^0:1\leq j\leq k\} \cup\{x_t^\theta:1\leq t\leq T,\ 1\leq\theta\leq\tau\}. \]
Write its distinct elements as \(\,s_1<\cdots<s_M\,\). Then \(\,M\leq k+T\tau\,\).
Lemma 1. Every placement can be replaced by a placement using only locations in \(\,S\,\), without increasing its cost.
Proof. First clip all facility locations to \(\,[s_1,s_M]\,\). Clipping fixes every agent location and starting location, decreases distances to agents, and is nonexpansive, so movement costs also do not increase.
If \(\,M=1\,\), the conclusion follows immediately. Otherwise, choose \(\,U\,\) uniformly from \(\,(0,1)\,\). Define a random map \(\,R:[s_1,s_M]\to S\,\) that fixes \(\,S\,\), and, for \(\,z\in(s_i,s_{i+1})\,\), satisfies
\[ R(z)= \begin{cases} s_{i+1},&U\leq (z-s_i)/(s_{i+1}-s_i),\\ s_i,&U>(z-s_i)/(s_{i+1}-s_i). \end{cases} \]
Use the same \(\,U\,\) for every location. Each realization of \(\,R\,\) is nondecreasing, and \(\,\mathbb E R(z)=z\,\). Consequently, for any \(\,z,z'\,\),
\[ \mathbb E|R(z)-R(z')|=|z-z'|. \]
Indeed, monotonicity fixes the sign of the difference, allowing expectation to pass through the absolute value.
Apply \(\,R\,\) to every facility location. For a type at \(\,x\in S\,\), choose an originally nearest facility \(\,j_*\,\). Since \(\,R(x)=x\,\),
\[ \mathbb E\min_j|x-R(y_j)| \leq\mathbb E|R(x)-R(y_{j_*})| =|x-y_{j_*}|. \]
Every movement term is preserved in expectation. Multiplying the service inequalities by the nonnegative coefficients \(\,a_\theta\,\) and summing gives \(\,\mathbb E C(R(y))\leq C(y)\,\).
For a fixed placement, the rounded placement takes only finitely many values. At least one therefore has cost at most its expectation. This proves the lemma.
Thus the continuous problem has the same optimum as the finite problem restricted to \(\,S\,\).
For each stage \(\,t\,\) and location \(\,s_i\,\), introduce fractional facility amounts \(\,c_i^t\geq0\,\). Let \(\,F_i^t\,\) denote cumulative amounts, enforced by
\[ F_0^t=0,\qquad F_M^t=k,\qquad F_i^t-F_{i-1}^t=c_i^t\quad(1\leq i\leq M). \]
The initial cumulative amounts are fixed constants:
\[ F_i^0=\#\{j:y_j^0\leq s_i\}. \]
For each type and stage, introduce assignment fractions \(\,z_{\theta i}^t\,\), constrained by
\[ \sum_{i=1}^{M}z_{\theta i}^t=1, \qquad 0\leq z_{\theta i}^t\leq c_i^t. \]
These constraints apply separately to each type; assignments of different types do not compete for capacity.
For each stage and gap \(\,i<M\,\), introduce \(\,h_i^t\,\) satisfying
\[ 0\leq h_i^t\leq k,\qquad h_i^t\geq F_i^t-F_i^{t-1},\qquad h_i^t\geq F_i^{t-1}-F_i^t. \]
Minimize
\[ V= \sum_{t=1}^{T}\sum_{\theta=1}^{\tau}\sum_{i=1}^{M} a_\theta |x_t^\theta-s_i|z_{\theta i}^t + \sum_{t=1}^{T}\sum_{i=1}^{M-1} (s_{i+1}-s_i)h_i^t. \]
The program is feasible: keep the initial facility amounts at every stage, set all movement variables to zero, and assign each type entirely to an occupied location. Its feasible region is bounded because
\[ 0\leq c_i^t,F_i^t,h_i^t\leq k,\qquad 0\leq z_{\theta i}^t\leq1. \]
It is therefore a nonempty compact rational polytope and has an attained optimum.
Take any placement on \(\,S\,\), retaining its original labels. Set \(\,c_i^t\,\) equal to the number of facilities at \(\,s_i\,\), and assign each type entirely to a nearest occupied location. The fractional service cost then equals the placement’s service cost.
For any two locations \(\,p,q\in S\,\),
\[ |p-q|= \sum_{i=1}^{M-1}(s_{i+1}-s_i) \left|\mathbf 1_{\{p\leq s_i\}}-\mathbf 1_{\{q\leq s_i\}}\right|. \]
At each cut \(\,s_i\,\), the triangle inequality gives
\[ \sum_{j=1}^{k} \left|\mathbf 1_{\{y_j^t\leq s_i\}} -\mathbf 1_{\{y_j^{t-1}\leq s_i\}}\right| \geq |F_i^t-F_i^{t-1}|. \]
Multiplying by gap lengths and summing shows that the placement’s movement cost is at least the LP movement cost obtained by setting \(\,h_i^t=|F_i^t-F_i^{t-1}|\,\).
Together with Lemma 1, this proves
\[ \operatorname{OPT}_{\mathrm{LP}}\leq \operatorname{OPT}_{\mathrm{original}}. \]
Fix any feasible LP solution. Define its quantile function by
\[ Q_t(u)=s_{\min\{i:F_i^t\geq u\}}, \qquad 0<u<k. \]
Order the original facility labels by their starting locations. Let \(\,\sigma\,\) be the resulting permutation, so that \(\,y_{\sigma(1)}^0\leq\cdots\leq y_{\sigma(k)}^0\,\).
Choose one offset \(\,U\,\) uniformly from \(\,(0,1)\,\), and set
\[ y_{\sigma(j)}^t(U)=Q_t(j-1+U), \qquad 1\leq j\leq k. \]
This assigns a complete trajectory to every original label. Moreover, since initial facility amounts are integers,
\[ Q_0(j-1+U)=y_{\sigma(j)}^0. \]
Thus the prescribed starting locations are respected exactly.
For every cut \(\,i<M\,\),
\[ \mathbf 1_{\{Q_t(u)\leq s_i\}} =\mathbf 1_{\{u\leq F_i^t\}}. \]
Applying the distance identity from Section 3 and integrating yields
\[ \int_0^k|Q_t(u)-Q_{t-1}(u)|\,du = \sum_{i=1}^{M-1}(s_{i+1}-s_i) |F_i^t-F_i^{t-1}|. \]
The intervals \(\,(j-1,j)\,\) partition \(\,(0,k)\,\). Hence
\[ \mathbb E\sum_{j=1}^{k} |y_{\sigma(j)}^t(U)-y_{\sigma(j)}^{t-1}(U)| = \int_0^k|Q_t(u)-Q_{t-1}(u)|\,du \leq\sum_{i=1}^{M-1}(s_{i+1}-s_i)h_i^t. \]
Fix a stage and an agent location \(\,x\,\). For \(\,r\geq0\,\), define the fractional facility amount within distance \(\,r\,\) by
\[ A(r)=\sum_{i:|s_i-x|\leq r}c_i^t. \]
The locations satisfying \(\,|s_i-x|\leq r\,\) form a consecutive block. Their quantile preimage is consequently an interval of length \(\,A(r)\,\).
An interval of length \(\,\ell\,\) in \(\,(0,k)\,\) contains at least one of the points
\[ U,\ 1+U,\ \ldots,\ k-1+U \]
with probability \(\,\min\{1,\ell\}\,\). For \(\,\ell<1\,\), its projection modulo one has measure \(\,\ell\,\). For \(\,\ell\geq1\,\), it contains an interval of length one and is hit for almost every offset.
Let \(\,D(U)=\min_j|x-y_{\sigma(j)}^t(U)|\,\). It follows that
\[ \mathbb P(D(U)>r)=\max\{0,1-A(r)\}. \]
Now consider any feasible assignment vector \(\,z_i\,\) for this type. Since \(\,\sum_i z_i=1\,\) and \(\,z_i\leq c_i^t\,\),
\[ \sum_{i:|s_i-x|>r}z_i =1-\sum_{i:|s_i-x|\leq r}z_i \geq\max\{0,1-A(r)\}. \]
Integrating these inequalities gives
\[ \mathbb E D(U) =\int_0^\infty\mathbb P(D(U)>r)\,dr \leq \int_0^\infty\sum_{i:|s_i-x|>r}z_i\,dr =\sum_i|s_i-x|z_i. \]
The integration identities follow directly by integrating indicators of intervals; all distances here are bounded.
This inequality holds separately for every type. Therefore it remains valid after multiplication by arbitrary nonnegative coefficients \(\,a_\theta\,\).
Summing the service and movement bounds proves, for every feasible LP solution,
\[ \mathbb E C(y(U))\leq V. \]
The rounded placement takes finitely many values, so some offset produces cost at most \(\,V\,\). Applying this to an optimal LP solution gives
\[ \operatorname{OPT}_{\mathrm{original}} \leq\operatorname{OPT}_{\mathrm{LP}}. \]
Combined with Section 3,
\[ \boxed{\operatorname{OPT}_{\mathrm{original}} =\operatorname{OPT}_{\mathrm{LP}}}. \]
Rounding can also be made deterministic in polynomial time. For a fixed rational LP solution, a rounded location changes only when
\[ U=F_i^t-(j-1). \]
Within \(\,(0,1)\,\), each cumulative amount contributes at most one such breakpoint. There are at most \(\,T(M-1)\,\) breakpoints. Sort them, choose a rational midpoint of each intervening interval, evaluate the resulting placements, and retain one of minimum cost. All breakpoints and midpoints have polynomial bit length.
The LP has
\[ O\bigl(T(\tau+1)M\bigr) \]
variables and constraints. Using cumulative variables as above, it also has only that many nonzero constraint coefficients. All numerical coefficients have polynomial bit length: they are obtained from input rationals by products and differences involving a constant number of factors.
Exact rational linear programming is solvable in time polynomial in its binary encoding length; see [the polynomial-time LP discussion in these Stanford notes](https://theory.stanford.edu/~trevisan/cs261/lecture05.pdf). Here the program is explicitly given, rational, feasible, and bounded, so the theorem applies.
Since \(\,M\leq k+T\tau\,\), the overall running time is
\[ \bigl(T(\tau+1)(k+T\tau)+L\bigr)^{O(1)} \]
bit operations. For the decision problem, one can simply add \(\,V\leq B\,\) and test rational LP feasibility. Sections 1–5 prove that this augmented LP is feasible exactly when a placement of cost at most \(\,B\,\) exists.
Thus binary-rational masses and weights admit a polynomial-time algorithm measured in support size, without expanding the society into individual agents.
⟨structured verdict parsed — rendered above⟩
The argument establishes polynomial-time solvability of the stated weighted, binary-rational support formulation. The discretization, LP relaxation, and rounding inequalities are correct. I found one minor qualification needed in the optional deterministic-rounding complexity statement; it does not affect the decision algorithm.
The substitution \(a_\theta=N\mu_\theta w_\theta\) is correct. Each coefficient is nonnegative and has bit length \(O(L)\): multiplication involves only three input rationals. Zero weights cause no difficulty.
The location set contains every starting location and every stage-specific agent location, and its size satisfies \(M\leq k+T\tau\).
Lemma 1 is valid:
The finite-outcome argument is also sound. The case \(M=1\) is explicitly handled. Consequently, restricting placements to the finite set preserves the optimum and supplies an attained minimum.
The cumulative constraints imply \(0\leq F_i^t\leq k\) and \(0\leq c_i^t\leq k\). The assignment constraints imply \(0\leq z_{\theta i}^t\leq1\).
The separate constraints \(z_{\theta i}^t\leq c_i^t\) correctly reflect the absence of shared service capacity: assignments of different types need not sum to at most the facility amount.
The proposed feasible solution works because \(k\geq1\), so an initially occupied location exists and has facility amount at least one. Keeping the initial amounts fixed makes all cumulative differences zero.
The region is closed, bounded, nonempty, and rational. Thus the stated attainment of the LP optimum is justified. When \(M=1\), the movement variables and movement sums are empty; the formulation remains valid.
The embedding of any placement on the finite location set into the LP is valid. Assigning each type wholly to a nearest occupied location satisfies the assignment constraints and reproduces its service cost.
The cut decomposition of distance is correct, including when an endpoint equals a cut location. Applying the triangle inequality at each cut gives the claimed lower bound on labeled movement.
The proposed movement variables satisfy their upper bounds because both cumulative counts lie in \([0,k]\). Therefore this embedding proves the stated inequality between the LP and original optima.
This step does not assume that the original labeled placement uses an optimal matching between consecutive stages.
The quantile function is well-defined for \(0<u<k\), since \(F_M^t=k\).
Ordering labels once by their starting locations and retaining that order throughout gives a complete trajectory for every original label. Integer initial cumulative amounts ensure that the rounded stage-zero locations equal the prescribed starting locations for every offset in \((0,1)\). Coincident starting locations and arbitrary ordering among their labels cause no problem.
For movement, the quantile indicator identity is correct. Integrating the cut decomposition yields exactly the cumulative-difference expression. Summing expectations over the unit quantile intervals then gives the claimed bound by the LP movement objective. Sharing one offset across stages is essential here and is explicitly specified.
This is the central weighted-extension step, and it is correct.
For each fixed type and radius, locations within that radius form a consecutive block. Its quantile preimage has length \(A(r)\); choices of interval endpoints affect only offsets of probability zero.
The asserted hitting probability is valid for an interval inside \((0,k)\):
Thus the displayed tail-probability identity follows.
The assignment-tail inequality uses precisely the two necessary constraints: total assignment is one, and assignment at each location is bounded by the fractional facility amount. Its direction is correct.
The integration identities are justified by bounded distances and finite sums. Therefore the expected service bound holds independently for every type. Multiplication by arbitrary nonnegative rational weights is valid; no expansion into individual agents is needed.
Summing the preceding bounds proves the expected total-cost inequality. A finite-valued rounded placement has some outcome of cost at most its expectation. Applying this to an attained optimal LP solution proves the reverse optimum inequality, hence exactness.
The breakpoint formula and count are correct: each internal cumulative amount contributes at most one breakpoint in \((0,1)\), and initial cumulative amounts contribute none.
Considering only open intervals between breakpoints is sufficient. These intervals carry all probability, and the placement is constant on each. Consequently, one of their representative placements has cost at most the expectation. Endpoint offsets need not be evaluated.
Minor issue: The statement that all breakpoints and midpoints have polynomial bit length needs a qualification concerning the chosen LP solution. An arbitrary rational feasible solution can have arbitrarily large encoding length even for a fixed input. Thus rationality alone does not imply polynomial bit length relative to \(L,T,k,\tau\).
Minimum clarification: Specify that deterministic rounding uses an exact LP solution of polynomial encoding length returned by the polynomial-time LP algorithm, or state the rounding complexity relative to the supplied solution’s encoding length. This is an expositional qualification, not a missing mathematical argument.
The variable and constraint counts are correct. Assignment-sum constraints contribute \(O(T\tau M)\) nonzero coefficients; cumulative and movement constraints contribute \(O(TM)\). Thus the claimed total sparsity bound holds.
The objective coefficients use a constant number of rational products and differences and have polynomial bit length. Initial cumulative counts and the bound \(k\) also have polynomial encoding length.
The invoked theorem is stated adequately: explicitly encoded rational LP feasibility and exact optimization are solvable in time polynomial in the binary encoding length. The cited [Stanford notes, Sections 2.4–2.5](https://theory.stanford.edu/~trevisan/cs261/lecture05.pdf) support this theorem and the existence of polynomial-size rational optimal solutions. The original LP is explicitly rational, feasible, and bounded. Adding the threshold constraint may make it infeasible, which the theorem also permits the algorithm to detect.
Both directions of decision equivalence are established:
The claimed polynomial running-time form follows. The decision algorithm itself does not require deterministic rounding, so the minor qualification above does not weaken the complexity classification.
⟨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.