Answer: Polynomial-time solvable exactly in \(m,\tau,L\), with \(m=1\).
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a strongly polynomial algorithm for com- puting transshipment allocation and pricing in WVT.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a unit-mass society with finite support \(T\) of \(\tau\) retailer types and rational masses \(\mu_\theta\), where each type specifies per-retailer excess supply \(e_\theta\), unmet demand \(d_\theta\), salvage value \(s_\theta\), selling price \(p_\theta\), shortage penalty \(\rho_\theta\), equity weight \(w_\theta\), and pairwise logistics costs \(\kappa_{\theta\phi}\), compute an optimal type-to-type flow \(x_{\theta\phi}\) and a transshipment price \(r_{\theta\phi}\) for each used pair. Require \(\sum_\phi x_{\theta\phi}\leq\mu_\theta e_\theta\), \(\sum_\theta x_{\theta\phi}\leq\mu_\phi d_\phi\), \(x_{\theta\phi}\geq0\), and \(s_\theta\leq r_{\theta\phi}\leq p_\phi+\rho_\phi-\kappa_{\theta\phi}\) on eligible pairs; maximize \(\sum_{\theta,\phi}x_{\theta\phi}[w_\theta(r_{\theta\phi}-s_\theta)+w_\phi(p_\phi+\rho_\phi-r_{\theta\phi}-\kappa_{\theta\phi})]\).
A unit-mass society for a single product is given by its support: a list \(T\) of \(\tau\) retailer types with positive binary-rational masses \(\mu_\theta\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type specifies nonnegative rational excess supply \(e_\theta\), unmet demand \(d_\theta\), salvage value \(s_\theta\), selling price \(p_\theta\), shortage penalty \(\rho_\theta\), and fixed equity weight \(w_\theta\), with \(e_\theta d_\theta=0\). Directed per-unit logistics costs \(\kappa_{\theta\phi}\) are nonnegative rationals paid by the receiver.
Let \(E=\{(\theta,\phi):\theta\ne\phi,\ e_\theta>0,\ d_\phi>0,\ s_\theta\le p_\phi+\rho_\phi-\kappa_{\theta\phi}\}\). Flows outside \(E\) are zero; no intermediate forwarding is allowed.
Choose divisible aggregate flows \(x_{\theta\phi}\ge0\) satisfying \(\sum_\phi x_{\theta\phi}\le\mu_\theta e_\theta\) and \(\sum_\theta x_{\theta\phi}\le\mu_\phi d_\phi\), and one per-unit price \(r_{\theta\phi}\in[s_\theta,p_\phi+\rho_\phi-\kappa_{\theta\phi}]\) for each used pair.
Compute a flow and prices maximizing \(\sum_{(\theta,\phi)\in E}x_{\theta\phi}[w_\theta(r_{\theta\phi}-s_\theta)+w_\phi(p_\phi+\rho_\phi-r_{\theta\phi}-\kappa_{\theta\phi})]\). Any optimum is acceptable.
Let \(L\) be the total binary input length; the number of products is fixed at \(m=1\).
Is this continuous allocation-and-pricing problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a finite list of retailers, a strongly polynomial algorithm for weighted-value transshipment allocation and pricing is stated in the [WVT algorithmic result](https://www.cse.iitb.ac.in/~swaprava/papers/inventory_control.pdf).
No result specifically addressing the support-encoded mass formulation was located in the search.
The problem is solvable exactly in polynomial time in \(\tau,L\), hence in \(m,\tau,L\) for the stipulated \(m=1\). The support masses become rational capacities in a linear program of polynomial size.
For each \((\theta,\phi)\in E\), define the receiver’s maximum acceptable price and the available surplus by
\(u_{\theta\phi}=p_\phi+\rho_\phi-\kappa_{\theta\phi},\qquad \Delta_{\theta\phi}=u_{\theta\phi}-s_\theta\ge 0.\)
For an admissible price \(r\in[s_\theta,u_{\theta\phi}]\), the weighted benefit per unit is
\(g_{\theta\phi}(r)=w_\theta(r-s_\theta)+w_\phi(u_{\theta\phi}-r)=w_\phi\Delta_{\theta\phi}+(w_\theta-w_\phi)(r-s_\theta).\)
This is affine in \(r\). Therefore:
When the weights are equal, every admissible price is optimal. In every case, the maximum weighted benefit per unit equals
\(c_{\theta\phi}=\max\{w_\theta,w_\phi\}\Delta_{\theta\phi}.\)
These prices depend only on the input. Their simultaneous use is feasible because the problem imposes no constraints coupling prices on different pairs.
For any feasible allocation and prices, nonnegativity of the flows gives
\(\displaystyle \sum_{(\theta,\phi)\in E}x_{\theta\phi}g_{\theta\phi}(r_{\theta\phi})\le \sum_{(\theta,\phi)\in E}c_{\theta\phi}x_{\theta\phi}.\)
Conversely, every feasible allocation attains equality when equipped with the prices \(r^*_{\theta\phi}\). Thus eliminating prices preserves the optimum exactly.
Define the aggregate supply and demand capacities by
\(a_\theta=\mu_\theta e_\theta,\qquad b_\theta=\mu_\theta d_\theta.\)
The remaining optimization is the following rational linear program:
\(\displaystyle \max_x\ \sum_{(\theta,\phi)\in E}c_{\theta\phi}x_{\theta\phi},\)
subject to
\(\displaystyle \sum_{\phi:(\theta,\phi)\in E}x_{\theta\phi}\le a_\theta\quad\text{for every }\theta\in T,\)
\(\displaystyle \sum_{\theta:(\theta,\phi)\in E}x_{\theta\phi}\le b_\phi\quad\text{for every }\phi\in T,\)
\(x_{\theta\phi}\ge 0\quad\text{for every }(\theta,\phi)\in E.\)
These are precisely the original flow constraints, with flows outside \(E\) fixed to zero.
The zero allocation is feasible. Moreover, each variable satisfies \(0\le x_{\theta\phi}\le a_\theta\). Consequently, the feasible set is closed and bounded, and the linear objective attains a finite maximum. If \(E\) is empty, the zero allocation already solves the problem.
Let \(x^*\) be an optimal solution of this linear program. For every used pair, output the price \(r^*_{\theta\phi}\) from Section 1. The resulting allocation and prices are feasible and achieve the linear program’s optimum. The inequality proved in Section 1 shows that no original feasible solution can do better. This proves correctness.
There are at most \(\tau(\tau-1)\) variables and at most \(2\tau+|E|\) inequalities, counting nonnegativity.
The set \(E\) can be constructed by testing each ordered pair using exact rational comparisons. Each capacity \(a_\theta,b_\theta\) and coefficient \(c_{\theta\phi}\) requires only a constant number of additions, subtractions, comparisons, and multiplications of input rationals.
To check encoding size explicitly, multiplying rationals multiplies their numerators and denominators, so their binary lengths add. Adding rationals can use the product of their denominators, again giving a length bounded by the sum of the operand lengths plus a constant. Because each derived coefficient uses a constant number of input values, its binary length is \(O(L)\). The constraint matrix has entries only in \(\{-1,0,1\}\). Thus the entire linear program has encoding length polynomial in \(\tau,L\).
We apply the standard rational linear programming theorem: a linear program with binary-encoded rational data can be solved in time polynomial in its encoding length, returning an exact rational optimum when it is feasible and has a finite optimum. Polynomial-time methods and recovery of an optimal vertex are discussed in [MIT’s notes on algorithms for linear programming](https://courses.csail.mit.edu/6.854/18/Notes/n14-LP_algorithms.html).
All hypotheses have been verified: the data are rational, the encoding is polynomial in size, and the program is feasible with a finite optimum. The returned allocation therefore has polynomial output length. Each recovered price is either an input salvage value or the rational expression \(p_\phi+\rho_\phi-\kappa_{\theta\phi}\), so prices also have polynomial output length.
The masses enter only through \(a_\theta=\mu_\theta e_\theta\) and \(b_\theta=\mu_\theta d_\theta\). The algorithm operates directly on the \(\tau\) listed types; it never expands a mass into individual retailers.
The linked [WVT paper, Theorem 3 and its appendix proof](https://www.cse.iitb.ac.in/~swaprava/papers/inventory_control.pdf), likewise eliminates prices before reducing allocation to bipartite weighted matching. The argument above independently handles rational mass capacities and proves the requested polynomial-time conclusion.
Accordingly, NP-hardness under polynomial-time reductions would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The price elimination is exact, the resulting rational linear program has polynomial encoding length, and the stated polynomial-time LP theorem applies. No major or minor mathematical gaps were found.
The argument addresses the specified continuous problem with \(m=1\), divisible aggregate flows, and independently chosen prices for used pairs. It treats \(\tau\) as the number of listed support types and never expands the rational masses into individual retailers.
The rationality of capacities and objective coefficients follows from the task’s rational input data, including the fixed equity weights. No extra integrality assumption is introduced.
For every \((\theta,\phi)\in E\), the definition of \(E\) guarantees
\[
u_{\theta\phi}\ge s_\theta,
\]
so the price interval is nonempty and \(\Delta_{\theta\phi}\ge0\).
The displayed expansion of \(g_{\theta\phi}(r)\) is algebraically correct. Its slope is \(w_\theta-w_\phi\), so the endpoint choices are correct in both strict cases. When the weights agree, the function is constant.
Evaluating at the selected endpoint gives exactly
\[
c_{\theta\phi}=\max\{w_\theta,w_\phi\}\Delta_{\theta\phi}.
\]
The independence assertion is justified by the task: there are no constraints coupling prices across different pairs. For each fixed feasible flow, all selected endpoint prices can therefore be used simultaneously.
Multiplying each per-unit upper bound by \(x_{\theta\phi}\ge0\) preserves its direction. Summing proves the stated objective upper bound. Conversely, the selected prices attain that bound for every feasible flow. This establishes equality of the original and reduced optimal values, rather than merely an upper bound.
The zero-flow case creates no difficulty: prices need only be output for used pairs.
The capacities \(a_\theta=\mu_\theta e_\theta\) and \(b_\theta=\mu_\theta d_\theta\) reproduce the original aggregate constraints exactly. Restricting variables to \(E\) enforces the requirement that all other flows vanish. No forwarding variables or additional feasible movements are introduced.
The zero allocation satisfies all constraints because capacities are nonnegative. Each variable is bounded above by its sender’s finite capacity, as the prover states. The feasible region is therefore closed and bounded in finite-dimensional space, and the continuous linear objective attains a finite maximum.
The empty-edge case is explicitly handled. This also covers instances with no eligible suppliers or receivers, including the possible single-type instance.
The reconstruction step is valid: an LP-optimal flow satisfies the original flow constraints, and every reconstructed price lies in its required interval.
The objective equals the LP optimum by the endpoint calculation. Every original feasible allocation and pricing has objective bounded above by the LP objective of its own flow, which in turn is bounded above by the LP optimum. The claimed global optimality follows.
The variable and inequality counts are correct: there are at most \(\tau(\tau-1)\) variables and \(2\tau+|E|\) inequalities when nonnegativity is included.
Constructing \(E\) requires only polynomially many exact rational tests. Each capacity, surplus, and objective coefficient uses a constant number of operations on input rationals.
The bit-length reasoning is sound: rational multiplication adds operand bit lengths up to a constant, and rational addition or subtraction permits a representation whose bit length is bounded by the sum of operand lengths up to a constant. Thus every derived scalar has length \(O(L)\). Together with the polynomial number of matrix entries, this yields a polynomial-size LP.
The argument concerns binary computation time, not merely a polynomial count of arithmetic operations.
The prover explicitly states the required standard theorem: binary-encoded rational LPs admit polynomial-time exact optimization when feasible with a finite optimum.
Its hypotheses are verified here: the LP is rational, explicitly represented with polynomial encoding length, feasible, and bounded. The cited [MIT LP notes](https://courses.csail.mit.edu/6.854/18/Notes/n14-LP_algorithms.html) discuss polynomial-time algorithms, rational vertex size bounds, and recovery of an optimal vertex.
Consequently, invoking exact rational LP optimization is justified. The polynomial output-length claim follows from that theorem. Reconstructed prices also have polynomial encoding length because they are input salvage values or the already bounded rational expressions \(p_\phi+\rho_\phi-\kappa_{\theta\phi}\).
The descriptive comparison with the [WVT paper](https://www.cse.iitb.ac.in/~swaprava/papers/inventory_control.pdf) is accurate: its appendix eliminates prices and constructs a weighted bipartite \(b\)-matching formulation. The prover does not rely on transferring that paper’s finite-retailer theorem to rational support masses; its independent LP argument establishes the requested result.
The conclusion is polynomial-time exact solvability for the stipulated \(m=1\). The final NP-hardness caveat is correct under the usual polynomial-time reduction interpretation.
Required repair or clarification: none.
⟨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.