Answers are grounded in this paper and cite their sources.
We study budgeted capacity augmentation for single-source single-sink under constant inflow u₀. The goal is to increase capacities on arcs subject to a global budget constraint in order to minimize the steady-state travel time in the network. We show that this problem is weakly NP-hard on series-parallel networks and provide an exact pseudopolynomial algorithm as well as a fully polynomial algorithm that attains the optimum travel time for budget B while spending at most B + ε·max,u₀\. On general networks the problem becomes strongly NP-hard. Moreover, unless P = NP, for every fixed ε ∈ (0,1), no polynomial-time algorithm can achieve the optimal steady-state travel time while exceeding the budget by at most a factor of n1-ε. Lastly, we give structural properties about steady-state travel time under varying arc capacities. We identify capacity thresholds determined by subsets of s-t-cuts and show that the travel time is constant in the interior of the cells resulting from the corresponding hyperplane arrangement.
No takes yet. Share an insight, caveat, or question.
Dahlmeier et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: