Answer: Exactly polynomial-time solvable; the threshold decision version belongs to \(\mathrm{P}\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe Neat Shifting Algorithm yields aggregate gap- minimizing assignments.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational target positions \(x_1<\cdots<x_\tau\) and positive rational masses \(\mu_i\) summing to \(1\), find the minimum of \(\sum_{i=1}^{\tau}\int_{\mathbb R}|x_i-y|\,d\pi_i(y)\) over nonnegative assignment measures satisfying \(\pi_i(\mathbb R)=\mu_i\) and \(\sum_i\pi_i(B)\leq |B|\) for every measurable set \(B\), where \(|B|\) is its length.
A society is given by its support: \(\tau\geq 1\) distinct rational target positions \(x_1<\cdots<x_\tau\) on \(\mathbb R\), each with positive binary-rational mass \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types.
An assignment consists of nonnegative finite Borel measures \(\pi_i\) on \(\mathbb R\), with \(\pi_i(\mathbb R)=\mu_i\) and \(\sum_i\pi_i(B)\leq\lambda(B)\) for every Borel set \(B\), where \(\lambda\) is Lebesgue measure. Mass may be split, and unused capacity is allowed.
The optimization problem is to find the exact minimum of \(\sum_{i=1}^{\tau}\int_{\mathbb R}|x_i-y|\,d\pi_i(y)\). Its threshold decision version additionally receives a binary-rational bound \(K\) and asks whether a feasible assignment has cost at most \(K\).
Let \(L\) be the total binary input length, including \(K\) when present. State running times in \(\tau\) and \(L\); there is no separate finite location parameter \(m\).
Is this continuous minimum-cost assignment problem solvable exactly in polynomial time, or is its threshold decision version NP-hard?
For explicitly listed \(n\) agents with integer targets and distinct assigned slots in \(\mathbb Z\), the Neat Shifting Algorithm minimizes total absolute distance in \(O(n^3)\) time. [Aziz et al.](https://research-api.cbs.dk/ws/portalfiles/portal/57305053/lars_peter_sterdal_et_al_computational_aspects_acceptedmanuscript.pdf)
No result settling the exact binary-input complexity of the continuous problem stated here was located in the literature search.
The continuous problem is exactly solvable in polynomial time. Its threshold decision version belongs to \(\mathrm{P}\).
More precisely, an optimal assignment exists in which each target receives Lebesgue measure on a single interval of length \(\mu_i\), with these intervals ordered by target. A finite algorithm computes their rational endpoints and the exact rational minimum using
\(O\!\left(\tau^3\log(\tau+1)\right)\)
arithmetic operations. A bit-complexity bound is
\(O\!\left(\tau^3\log(\tau+1)\bigl(L+\tau\log(\tau+1)\bigr)^2\right)\).
The proof below treats the continuous model directly; the integer-slot setting of the [cited Aziz et al. paper](https://research-api.cbs.dk/ws/portalfiles/portal/57305053/lars_peter_sterdal_et_al_computational_aspects_acceptedmanuscript.pdf) is background.
Define cumulative masses
\(s_0=0,\qquad s_i=\sum_{h=1}^{i}\mu_h,\qquad s_\tau=1.\)
Let \(X:(0,1)\to\mathbb R\) be the target quantile function: \(X(s)=x_i\) for \(s_{i-1}<s<s_i\).
Consider a feasible assignment, and write \(\nu=\sum_i\pi_i\) for its aggregate assigned measure. This is a probability measure satisfying \(\nu\leq\lambda\). Its cumulative distribution function \(F_\nu\) therefore satisfies, for \(u<v\),
\(0\leq F_\nu(v)-F_\nu(u)=\nu((u,v])\leq v-u.\)
In particular, \(F_\nu\) is continuous. Define its quantile function by
\(q(s)=\inf\{y:F_\nu(y)\geq s\},\qquad 0<s<1.\)
The probability-measure limits at infinity and continuity imply that \(q(s)\) is finite and \(F_\nu(q(s))=s\). Consequently, for \(0<u<v<1\),
\(v-u=F_\nu(q(v))-F_\nu(q(u))\leq q(v)-q(u).\)
Thus
\(z(s)=q(s)-s\)
is nondecreasing.
We next show that assigning target \(X(s)\) to location \(q(s)\) cannot increase cost.
Let \(\sigma=\sum_i\mu_i\delta_{x_i}\). For any real \(x,y\),
\(|x-y|=\int_{\mathbb R}|\mathbf 1_{\{x\leq t\}}-\mathbf 1_{\{y\leq t\}}|\,dt.\)
For the original assignment, define
\(A(t)=\sum_{x_i\leq t}\pi_i((t,\infty)),\qquad B(t)=\sum_{x_i>t}\pi_i((-\infty,t]).\)
Tonelli’s theorem applies because the integrands are nonnegative. It gives
\(\sum_i\int|x_i-y|\,d\pi_i(y)=\int_{\mathbb R}(A(t)+B(t))\,dt.\)
Moreover, \(A(t)-B(t)=F_\sigma(t)-F_\nu(t)\), so the original cost is at least
\(\int_{\mathbb R}|F_\sigma(t)-F_\nu(t)|\,dt.\)
For the quantile assignment, the sets \(\{s:X(s)\leq t\}\) and \(\{s:q(s)\leq t\}\) are initial intervals of lengths \(F_\sigma(t)\) and \(F_\nu(t)\). Their symmetric difference therefore has length \(|F_\sigma(t)-F_\nu(t)|\). Applying the same identity and Tonelli’s theorem yields
\(\int_0^1|X(s)-q(s)|\,ds=\int_{\mathbb R}|F_\sigma(t)-F_\nu(t)|\,dt.\)
The quantile assignment has aggregate measure \(\nu\), hence remains feasible, and its cost is no larger than the original cost.
We need the following elementary lemma.
Lemma. Suppose \(a<b\), \(x\in\mathbb R\), and \(z:(a,b)\to\mathbb R\) is nondecreasing. There is a finite constant \(c\) satisfying
\(\inf_{(a,b)}z\leq c\leq\sup_{(a,b)}z\)
and, almost everywhere on \((a,b)\),
\(|s+c-x|\leq |s+z(s)-x|.\)
Proof. The function \(h(s)=s+z(s)\) is strictly increasing. There are three cases.
If \(h(s)<x\) throughout the interval, set \(c=\sup z\). Monotonicity and the limit as \(s\) approaches \(b\) give \(c\leq x-b\), so \(c\) is finite and
\(s+z(s)\leq s+c<x.\)
The claimed inequality follows.
If \(h(s)\geq x\) throughout the interval, set \(c=\inf z\). Taking the limit as \(s\) approaches \(a\) gives \(c\geq x-a\), so \(c\) is finite and
\(x<s+c\leq s+z(s).\)
Again the inequality follows.
Otherwise, there is \(r\in(a,b)\) such that \(h(s)<x\) for \(s<r\), and \(h(s)\geq x\) for \(s>r\). The one-sided limits satisfy
\(z(r-)\leq x-r\leq z(r+).\)
Set \(c=x-r\). For \(s<r\),
\(s+z(s)\leq s+c<x,\)
whereas for \(s>r\),
\(x<s+c\leq s+z(s).\)
These inequalities prove the assertion except possibly at the single point \(r\), which does not affect the integral. They also place \(c\) between the infimum and supremum of \(z\). \(\square\)
Apply the lemma to each interval \((s_{i-1},s_i)\), with \(x=x_i\). Let the resulting constants be \(c_i\). Because \(z\) is nondecreasing,
\(\sup_{(s_{i-1},s_i)}z\leq\inf_{(s_i,s_{i+1})}z,\)
so
\(c_1\leq c_2\leq\cdots\leq c_\tau.\)
The replacement \(q(s)=s+c_i\) on each mass interval does not increase cost. It assigns target \(i\) the interval
\(I_i=[s_{i-1}+c_i,\ s_i+c_i].\)
Its length is \(\mu_i\), and the intervals have disjoint interiors because
\(s_i+c_i\leq s_i+c_{i+1}.\)
Thus the measures \(\pi_i=\lambda|_{I_i}\) are feasible.
Conversely, every nondecreasing vector \((c_1,\ldots,c_\tau)\) defines such a feasible assignment. We have therefore reduced the original problem exactly to
\(\min_{c_1\leq\cdots\leq c_\tau}\sum_{i=1}^{\tau}F_i(c_i),\qquad F_i(c)=\int_{s_{i-1}}^{s_i}|s+c-x_i|\,ds.\)
This argument applies to every finite-cost feasible assignment. Such assignments exist, for example by assigning consecutive intervals inside \([0,1]\).
Put
\(\ell_i=x_i-s_i,\qquad u_i=x_i-s_{i-1}.\)
Then \(u_i-\ell_i=\mu_i>0\), and changing variables gives
\(F_i(c)=\int_{\ell_i}^{u_i}|c-t|\,dt.\)
Explicitly,
\( F_i(c)= \begin{cases} \mu_i\bigl((\ell_i+u_i)/2-c\bigr),&c\leq\ell_i,\\ \bigl((c-\ell_i)^2+(u_i-c)^2\bigr)/2,&\ell_i\leq c\leq u_i,\\ \mu_i\bigl(c-(\ell_i+u_i)/2\bigr),&c\geq u_i. \end{cases} \)
Each function is convex and continuously differentiable, with derivative
\(F_i'(c)=2\min\{\max\{c-\ell_i,0\},\mu_i\}-\mu_i.\)
The minimum is attained. Indeed,
\(F_i(c)\geq\mu_i|c|-\int_{\ell_i}^{u_i}|t|\,dt.\)
Because every \(\mu_i\) is positive, the objective tends to infinity when the maximum absolute coordinate tends to infinity. Hence its sublevel sets are bounded. The feasible set is closed and nonempty, so continuity gives a minimizer. The set of minimizers is compact.
For every consecutive block \(B=\{a,a+1,\ldots,b\}\), define
\(H_B(c)=\sum_{i=a}^{b}F_i(c),\)
and let \(r_B\) be its smallest minimizer.
This value exists: \(H_B'\) is continuous and nondecreasing, equals \(-\sum_{i\in B}\mu_i<0\) sufficiently far to the left, and equals \(\sum_{i\in B}\mu_i>0\) sufficiently far to the right. Its zero set is therefore a nonempty compact interval.
Define the candidate set
\(\mathcal C=\{r_B:B\text{ is a nonempty consecutive block}\}.\)
It contains at most \(\tau(\tau+1)/2\) values.
Claim. There is an optimal vector whose coordinates all belong to \(\mathcal C\).
Proof. Choose the lexicographically smallest optimal vector \(c^*\). This exists by successively minimizing coordinates over the compact set of optimal vectors.
Partition \(c^*\) into maximal consecutive blocks of equal coordinates. Consider one such block \(B\), whose common value is \(v\). Its neighboring coordinates, when present, are strictly smaller or strictly larger. Thus sufficiently small changes of \(v\), in either direction and throughout the block, preserve feasibility.
Optimality consequently implies \(H_B'(v)=0\), so \(v\) minimizes \(H_B\).
Suppose \(v>r_B\). Convexity implies that \(H_B\) is constant on \([r_B,v]\), since both endpoints minimize it. Lowering the block value by a sufficiently small positive amount therefore preserves feasibility and the total objective. The resulting vector is lexicographically smaller, contradicting the choice of \(c^*\).
Hence \(v=r_B\). This holds for every maximal block, proving the claim. \(\square\)
For a block \(B\),
\(H_B'(c)=2\sum_{i\in B}\min\{\max\{c-\ell_i,0\},\mu_i\}-\sum_{i\in B}\mu_i.\)
Its breakpoints are the \(2|B|\) rational endpoints \(\ell_i,u_i\). Sort these endpoints and sweep from left to right, maintaining the derivative and its slope. The slope increases by \(2\) at each \(\ell_i\) and decreases by \(2\) at each \(u_i\), processing coincident events together.
The first zero determines \(r_B\). If a zero interval occurs, choose its left endpoint. Otherwise, on a segment starting at endpoint \(e\), with derivative \(d<0\) and positive slope \(2k\), the zero is exactly
\(r_B=e-\frac{d}{2k},\qquad 1\leq k\leq |B|.\)
Thus every candidate is rational. Sorting and sweeping a block takes \(O(|B|\log(|B|+1))\) arithmetic operations.
Sort the distinct candidates as
\(v_1<v_2<\cdots<v_M,\qquad M\leq\tau(\tau+1)/2.\)
Let \(A(i,j)\) be the minimum cost for the first \(i\) targets, using nondecreasing candidate values and requiring the \(i\)-th value to equal \(v_j\). Then
\(A(1,j)=F_1(v_j)\)
and
\(A(i,j)=F_i(v_j)+\min_{k\leq j}A(i-1,k).\)
The recurrence follows because precisely the candidate values indexed by \(k\leq j\) may precede \(v_j\).
Prefix minima compute each row in \(O(M)\) operations. By the candidate-set claim, the exact continuous optimum is
\(\min_{1\leq j\leq M}A(\tau,j).\)
Backtracking gives an optimal vector, hence the optimal assignment \(\pi_i=\lambda|_{I_i}\).
Computing all block candidates takes \(O(\tau^3\log(\tau+1))\) arithmetic operations. Candidate sorting, function evaluation, and the dynamic program fit within this bound.
It remains to bound the sizes of the numbers manipulated.
Let \(D\) be the product of all input denominators, including that of \(K\) when present. Its binary length is \(O(L)\). All cumulative masses and endpoints are integer multiples of \(1/D\).
At a sweep endpoint, the derivative is also an integer multiple of \(1/D\). The root formula therefore shows that each candidate has denominator dividing \(2kD\) for some \(1\leq k\leq\tau\); endpoint candidates satisfy the same bound.
Set
\(Q=2D\,\tau!,\qquad W=2Q^2.\)
Every candidate and every endpoint is an integer multiple of \(1/Q\). The explicit formulas for \(F_i\) then show that every candidate cost is an integer multiple of \(1/W\). All dynamic-programming costs can consequently be stored as integers with common denominator \(W\).
Candidates lie between the smallest and largest endpoints of their blocks. Together with the input magnitude bounds, this implies that all scaled integers used by the algorithm have
\(O\!\left(L+\tau\log(\tau+1)\right)\)
bits, including sums of costs. Using schoolbook integer arithmetic yields the stated bit-complexity bound
\(O\!\left(\tau^3\log(\tau+1)\bigl(L+\tau\log(\tau+1)\bigr)^2\right).\)
Finally, \(K\) is also an integer multiple of \(1/W\), since its denominator divides \(D\). Comparing the exact minimum with \(K\) therefore requires an exact integer comparison.
This proves polynomial-time exact optimization and polynomial-time threshold decision in the stated binary-input model.
⟨structured verdict parsed — rendered above⟩
The argument establishes polynomial-time exact optimization and threshold decision. I found no substantive mathematical or complexity error. There is one minor definitional omission: the target quantile function is not assigned values at its internal mass boundaries.
The aggregate measure \(\nu=\sum_i\pi_i\) is a probability measure because its total mass is \(\sum_i\mu_i=1\). The capacity constraint gives \(\nu\leq\lambda\), and therefore the asserted bound
\[
0\leq F_\nu(v)-F_\nu(u)\leq v-u
\]
is correct. In particular, the distribution function is continuous.
For each \(s\in(0,1)\), the probability-measure limits at infinity ensure that the quantile \(q(s)\) is finite. Continuity gives \(F_\nu(q(s))=s\), including when the distribution function has flat intervals. Consequently, the inequality
\[
q(v)-q(u)\geq v-u
\]
is valid, and \(z(s)=q(s)-s\) is nondecreasing.
The pointwise indicator identity for absolute distance is correct. Every integrand used in the applications of Tonelli’s theorem is nonnegative and measurable; the applications therefore remain valid even when the original cost is infinite.
The identity \(A(t)-B(t)=F_\sigma(t)-F_\nu(t)\) follows from the prescribed marginal masses. Taking absolute values gives the stated lower bound on the original cost.
The quantile assignment attains this lower bound: both indicator sets in the quantile parameter are initial intervals, up to endpoints of measure zero. Their symmetric difference has the asserted length. The pushforward of Lebesgue measure on \((0,1)\) under \(q\) is \(\nu\), so the aggregate capacity constraint is preserved. Each target receives its prescribed mass.
Minor issue: \(X\) is declared to be a function on all of \((0,1)\), but its definition excludes the internal boundaries \(s_1,\ldots,s_{\tau-1}\). This has no effect on any integral or assignment.
Minimum clarification: Assign arbitrary values to \(X\) at these finitely many points, or explicitly define \(X\) only almost everywhere.
The lemma is correct.
The three cases cover all possibilities, including a point where \(h(s)=x\).
The bounds placing each \(c_i\) between the corresponding infimum and supremum of \(z\) imply \(c_i\leq c_{i+1}\). Thus the resulting intervals have disjoint interiors. Shared endpoints have zero Lebesgue measure, so they do not violate capacity.
The converse construction from any nondecreasing vector is also valid. The argument therefore establishes equality of the continuous infimum and the finite convex problem’s infimum. The explicitly supplied finite-cost assignment makes exclusion of infinite-cost assignments harmless.
The change of variables giving
\[
F_i(c)=\int_{\ell_i}^{u_i}|c-t|\,dt
\]
is correct.
I checked all three branches of the explicit formula and their derivatives. The formulas agree at both breakpoints, and the derivative is continuous and nondecreasing. Thus the asserted convexity and continuous differentiability hold.
The coercivity argument is valid. Since every mass is strictly positive and there are finitely many coordinates, the displayed lower bound forces the objective to tend to infinity when the largest absolute coordinate tends to infinity.
The feasible set is nonempty and closed. Continuity and bounded sublevel sets therefore establish attainment and compactness of the optimizer set. Together with the interval reduction, this also proves existence of an optimal continuous assignment.
For every nonempty consecutive block, the derivative of \(H_B\) is continuous and nondecreasing, with strictly negative and strictly positive tails. Its zero set is a nonempty compact interval, so its smallest minimizer exists.
The candidate-set argument is sound:
This establishes that every coordinate of the selected optimizer belongs to the candidate set. First and last blocks, and the case of a single block, are covered by the same argument.
The breakpoint sweep is also correct. Each lower endpoint increases the derivative’s slope by \(2\), and each upper endpoint decreases it by \(2\). Grouping coincident events handles ties. The root formula on a segment with positive slope has the correct sign and denominator. Selecting the first zero handles flat minimizer intervals correctly.
The dynamic-programming states and recurrence describe precisely the feasible nondecreasing candidate sequences. Prefix minima compute the stated transitions, and the candidate-set result ensures that restricting to these states preserves the exact optimum.
Backtracking supplies the interval endpoints and hence a finite exact representation of an optimal assignment.
There are at most \(\tau(\tau+1)/2\) candidates. Summing the stated block computation costs yields \(O(\tau^3\log(\tau+1))\) arithmetic operations. Sorting the candidate set and performing the dynamic program fit within this bound.
The denominator argument is valid:
The candidate range bound and input magnitude bounds justify \(O(L+\tau\log(\tau+1))\) bits for the scaled integers, including accumulated costs. Schoolbook arithmetic therefore supports the claimed bit-complexity bound.
No expansion into a number of agents proportional to a mass denominator occurs. The running time depends on the support size and binary input length as required.
The proof covers \(\tau=1\), coincident breakpoints, duplicate candidates, nonunique block minimizers, arbitrarily small positive masses, and negative thresholds. For \(\tau=1\), its formulas yield the centered interval and minimum \(1/4\), consistently with total mass one.
The discrete Neat Shifting Algorithm is used only as background; the continuous result does not depend on transferring its complexity guarantee.
The only requested repair is the harmless definition of \(X\) at its internal boundaries.
⟨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.