Metraipolis › archive › dc_1cd233c97e9e
Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm — arXiv:2611.01387
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01387
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:45:24.801Z
- SHA-256 of the archived text
5e792add8b778d9882ffecfe08aaea77608572d342ab3d50dd76cfdd7ba280a3- Stable URL of this page
https://metraipolis.com/documento/dc_1cd233c97e9e
How to cite
Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm — arXiv:2611.01387 — arXiv (en), https://arxiv.org/abs/2611.01387 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1cd233c97e9e (Metraipolis archive dc_1cd233c97e9e, sha256 5e792add8b778d9882ffecfe08aaea77608572d342ab3d50dd76cfdd7ba280a3)
BibTeX
@misc{dc1cd233c97e9e,
title = {Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm — arXiv:2611.01387},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01387},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1cd233c97e9e; sha256 5e792add8b778d9882ffecfe08aaea77608572d342ab3d50dd76cfdd7ba280a3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01387. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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\times50$ 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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno). Categorie arXiv: Optimization and Control (math.OC) ; Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2611.01387 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T18:14:37.758Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).