Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm
Abstract
The three-phase time minimization transportation problem partitions the origin-terminal links into three sets used in consecutive phases and minimizes the sum of the phase shipment times. Optimal solutions may leave a phase idle, as in the main example of the original study. We require every phase to carry a positive integer quantity while leaving the split of the total requirement across phases free. Discarding idle solutions from the original algorithm does not, in general, solve this variant. We prove that the optimum is attained by fixing one witness link in each of two phases and deciding the third phase by a single network flow computation, with the optimal Phase-3 time of each witness pair located by binary search. The resulting exact algorithm is strongly polynomial. It extends to any fixed number of phases, whereas, when the number of phases is part of the input, even non-idle feasibility is strongly NP-complete; feasibility alone is fixed-parameter tractable in the number of phases via known rainbow-matching results. We also characterize the minimum time of each phase. On the main example, non-idleness raises the optimum from 38 to 41. On 3,650 random instances with up to 50×50 links the algorithm took at most 50.2 seconds, and non-idleness raised the optimal value in 41% of the 2,250 instances with equal phase sizes; on 90 sampled instances it was faster than a mixed integer programming solver on 80 with a direct formulation and on 65 with a tighter threshold formulation.
Related
- A Polynomial-Time Algorithm for the Minimal Input/Output Node Cardinality Disturbance Decoupling Problem via Output Feedback
- A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
- A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem
- An Alternating Minimization Algorithm for Federated Sparse Orthogonal Nonnegative Matrix Factorization
- A restart-free accelerated algorithm for nonconvex minimization: continuous- and discrete-time analysis
BibTeX
@misc{kamalahasan2026threephase,
title = {{Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm}},
author = {Sailesh Kamalahasan and Raghav Paladugu and Archana Khurana},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01387},
eprint = {2611.01387},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01387},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm
AU - Sailesh Kamalahasan
AU - Raghav Paladugu
AU - Archana Khurana
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01387
UR - https://arxiv.org/abs/2611.01387
AB - The three-phase time minimization transportation problem partitions the origin-terminal links into three sets used in consecutive phases and minimizes the sum of the phase shipment times. Optimal solutions may leave a phase idle, as in the main example of the original study. We require every phase to carry a positive integer quantity while leaving the split of the total requirement across phases free. Discarding idle solutions from the original algorithm does not, in general, solve this variant. We prove that the optimum is attained by fixing one witness link in each of two phases and deciding the third phase by a single network flow computation, with the optimal Phase-3 time of each witness pair located by binary search. The resulting exact algorithm is strongly polynomial. It extends to any fixed number of phases, whereas, when the number of phases is part of the input, even non-idle feasibility is strongly NP-complete; feasibility alone is fixed-parameter tractable in the number of phases via known rainbow-matching results. We also characterize the minimum time of each phase. On the main example, non-idleness raises the optimum from 38 to 41. On 3,650 random instances with up to 50×50 links the algorithm took at most 50.2 seconds, and non-idleness raised the optimal value in 41% of the 2,250 instances with equal phase sizes; on 90 sampled instances it was faster than a mixed integer programming solver on 80 with a direct formulation and on 65 with a tighter threshold formulation.
ER -