Complexity Analysis of a Bicriteria Directed Multimodal Transportation Network Design Problem

Dominik Leib; Neele Leith\"auser; Susanne Fritzler

REVIEW 5 major objections 4 minor 25 references

Complexity Analysis of a Bicriteria Directed Multimodal Transportation Network Design Problem

T0 review · 5 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves the bicriteria public-transport network design problem is NP-complete even when all weights, demands, and mode parameters are 1, and that no polynomial-factor approximation exists for the general optimisation version…

desk verdict A new bicriteria multimodal network design problem with plausible NP-hardness results, but the fixed-flow PTAS/FPTAS proof has a real complexity gap and several smaller errors need repair. read the letter →

arxiv 2507.07894 v2 pith:4Q4FVXNY submitted 2025-07-10 math.OC

Dominik Leib , Susanne Fritzler , Neele Leithäuser This is my paper · ORCID

classification math.OC MSC 68Q1790B1090C2790C29

keywords bicriteriaoptimizationnetworkdesignNP-completenessinapproximabilitypublictransportationplanningknapsackproblemParetofrontierdirectedgraphs

topics P versus NP

open problems P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper analyses the Modal Split Problem (MSP), a model for choosing which links of a public-transport network to build, how many vehicles to run, and how passengers should be routed, while balancing passenger travel time against total energy use under a construction budget. The authors prove that even the most stripped-down version of this problem is NP-complete: with unit edge weights, a single public mode, unit demand between every pair of nodes, and unit energy and time coefficients, deciding whether a feasible plan meets given travel-time and energy bounds is already hard. They further prove that the optimisation version, minimising energy subject to a travel-time limit, cannot be approximated within any polynomial-time-computable factor $\alpha(|V|)$ unless P=NP, even when the travel-time bound is removed. On the positive side, they show that when passenger flows are fixed the remaining difficulty is a knapsack-type procurement problem, which admits a PTAS and, for a single mode, an FPTAS; they also identify a line segment of the relaxed problem's Pareto frontier that yields genuinely Pareto-optimal layouts under an ordering condition on mode parameters.

What carries the argument

The argument runs through three constructions. Lemma 3.1 shows the directed Network Design Problem DiNDP is NP-complete even with unit weights and distances by rebuilding a symmetric subgraph from an Exact-3-Cover instance, then Theorem 3.2 reduces DiNDP to MSP by setting the public-mode energy coefficient to $\eta_1=1$, private-transport energy so high that any feasible solution must be connected, and identifying construction cost with energy and routing cost with travel time. Inapproximability is carried by the directed Steiner tree problem: Theorem 3.4 plants demand $\lceil\alpha(n)(|E|+1)\rceil$ on each Steiner commodity so that an $\alpha$-approximation of energy would decide whether a bounded-cost arborescence exists. The fixed-flow results translate MSP into a Multidimensional Knapsack or Unbounded Knapsack instance whose variables are vehicle counts per edge and whose items record energy savings, construction cost, and passenger load; the known PTAS/FPTAS for knapsack then transfer back. Finally, the Pareto-frontier statement uses the geometric ordering of mode direction vectors $(\tau_i-\tau_0,\eta_i/k_i-\eta_0)$: for the steepest mode, a line segment between the all-private solution and the scaled single-mode solution is undominated in the relaxation.

What would settle it

Run the Theorem 3.4 construction on a Directed Steiner Tree instance whose optimal arborescence costs more than the budget $B$: the reduction predicts that every feasible MSP solution must place at least one passenger on private transport, forcing energy at least $\lceil\alpha(n)(|E|+1)\rceil$, so any claimed $\alpha$-approximation that returns energy at most $\alpha(n)|E|$ would simultaneously decide DiSTP and refute the inapproximability claim, unless the reduction itself is wrong.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the Modal Split Problem is intractable in a very robust sense and that its tractable parts are exactly the ones reducible to knapsack. Theorem 3.2 proves NP-completeness of MSP even with $w(e)=1$, $m=1$, $D(u,v)=1$ for all $u\neq v$, and $\eta_1=\tau_1=1$, by reducing the directed network design problem DiNDP to MSP; this is the strongest possible parameter collapse short of making the problem empty. Theorem 3.4 proves that for any polynomial-time computable function $\alpha(|V|)$, the optimisation version with $a=\infty$ is not $\alpha(|V|)$-approximable unless P=NP, via a reduction from Directed Steiner Tree in which a large demand $\lceil\alpha(n)(|E|+1)\rceil$ forces any approximation to separate feasible from infeasible Steiner instances. Section 4 shows NP-completeness persists when the passenger flow is fixed, when the graph is tree-like, and even when the graph is a single edge, and derives a PTAS/FPTAS for fixed-flow MSP from known approximation schemes for multidimensional and ordinary knapsack. The paper also proves that for instances whose mode parameters satisfy a slope-ordering condition, a specific line segment in the objective space lies on the Pareto frontier of a continuous relaxation, and every integral layout on it is Pareto-optimal for the original problem.

Load-bearing premise

The paper's fixed-flow approximation theorem assumes that writing out one knapsack item for each vehicle copy and each partial-fill level remains polynomial; with binary-encoded demands the list can be exponentially long, so the PTAS/FPTAS claim depends on an encoding argument that is not supplied.

Editorial extensions

If this is right

Even with unit weights, one mode, and unit demands, MSP has no polynomial-time exact algorithm unless P=NP, so exact optimisation for such problems is inherently exponential in the worst case.
For the general energy-minimisation version, no polynomial-time algorithm can guarantee any factor $\alpha(|V|)$ in the number of nodes, so approximation guarantees for MSP must come from additional structure rather than from a universal bound.
When the passenger flow is fixed, the leftover problem is a vehicle procurement problem with knapsack structure: a PTAS exists, and with one mode an FPTAS exists, giving practical near-optimal energy layouts.
For instances satisfying the slope-ordering condition, the relaxed problem has a known undominated line segment in objective space, and integral points on it are genuinely Pareto-optimal solutions to the original problem.
The directed versions of the underlying network design problems are likewise hard: DiNDP is NP-complete and cannot be approximated within $|V|^{1-\varepsilon}$ unless P=NP.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The positive fixed-flow theorem as written needs a compact encoding: the construction in Theorem 4.2 lists $\lfloor F(e)/k_i\rfloor$ copies and every partial-fill level $f$, which can be exponential in the bit length of the demand; a polynomial-time scheme therefore requires aggregation or a different encoding.
Reading the one-edge and tree-like hardness cases together suggests that the intrinsic difficulty of transit frequency setting lies in vehicle-type choice and fill constraints, not in route choice; knapsack-style approximation is the right tool for the procurement stage.
The relaxation's Pareto segment can serve as an outer bound in exact algorithms: any candidate solution whose objective point lies strictly below the segment cannot be Pareto-optimal for the integer problem, so the segment could prune a branch-and-bound search.
A concrete stress test: take a single-edge instance with $F(e)=2^p$ and $k_1=3$ and measure whether the claimed FPTAS run time stays polynomial in $p$; if it does not, the theorem needs a compact item representation.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take on arXiv:2507.07894. The paper defines a new bicriteria multimodal network design problem (MSP) and maps out its complexity: NP-complete in very stripped-down cases, no α(|V|)-approximation unless P=NP, and a claimed PTAS/FPTAS when the passenger flow is fixed. The hardness results look essentially right. The reductions from X3C and DiSTP are standard but adapted to a directed setting that genuinely seems to have been missing; Lemma 3.5 (the 2-approximation via shortest-path arborescences) is a clean observation. The model itself is reasonable and the paper is honest about what it does and doesn't cover.

The soft spots are real, though mostly repairable. In Theorem 3.2 the instance parameter assignment is reversed: it sets (a,b)=(β,γ) but then uses H≤a and T≤γ, which only works if a=γ and b=β. The integrality step is fine after that swap. In Theorem 4.1(a) the algebra has errors: the base energy should be 2Σ (with demand 2 on each edge) so b should be 2Σ−A, not Σ−A, and the inequality direction in the subset-sum conclusion is backwards. The intended reduction still works, but as written it doesn't parse.

The bigger problem is Theorem 4.2. The PTAS/FPTAS proofs construct MKPS/KPS instances by adding one item per vehicle copy and one item per partial-fill value. Flows and capacities are given in binary, so the number of copies floor(F(e)/k_i) and the range of f can be exponential in the input length. No compact encoding of multiplicities is provided, so the reduction is not polynomial and the approximation schemes are not established. The stress-test note is right on this; it's a load-bearing gap in the claimed positive results. It may be fixable via binary splitting or a different DP, but it is not a typo.

Overall: I'd send this to a serious referee rather than desk-reject. The core complexity claims are likely correct and valuable for the transportation network design community. The authors need a major revision: fix the parameter swap, the algebra, and either repair the PTAS proof or qualify the claim. The paper deserves a round of review; it just shouldn't be accepted as is.

Referee Report

5 major / 4 minor

Summary. The paper introduces the Modal Split Problem (MSP), a bicriteria directed network design model for public transport planning, and analyzes its complexity. The main hardness results are: MSP is NP-complete even with unit edge weights, a single mode, unit demands, and unit mode parameters (Theorem 3.2); the optimization version is not approximable within any polynomial-time computable function alpha(|V|) unless P=NP (Theorem 3.4); and MSP remains NP-complete when the passenger flow is fixed or when the graph is a single edge (Theorem 4.1). The paper also claims a PTAS for fixed-flow MSP and an FPTAS for the single-mode fixed-flow case (Theorem 4.2), together with a geometric characterization of a Pareto-frontier segment for a continuous relaxation (Theorems 4.3 and 4.4) and a sampling algorithm. An appendix proves NP-completeness and inapproximability for the directed network design problem DiNDP.

Significance. The hardness results, if correct, are significant: they show that even extremely stripped-down versions of a practically motivated bicriteria transit design problem are intractable, and that no general approximation guarantee exists. The paper also contains useful transfer arguments from undirected to directed network design, and the Pareto-frontier relaxation result is an appealing geometric idea that could be valuable for practitioners. The reductions are from standard NP-complete problems (X3C, SSUM, UKPS, DiSTP) and are checkable in principle. However, as written the positive approximability claims in Theorem 4.2 are not established, and several load-bearing steps in Theorems 3.2 and 4.1(a) contain inconsistencies. The manuscript therefore needs substantial revision before its claims can be accepted.

major comments (5)

[Section 4, Theorem 4.2 proof, items i)-ii)] The constructed MKPS/KPS instance is not polynomial in the input size. Since F(e_j) and k_i are binary integers, the number of full-vehicle copies floor(F(e_j)/k_i) and the number of partial-fill values f in [ceil(eta_i/eta_0), min(k_i,F(e_j))] can both be exponential; for example, F(e_j)=2^N with k_i=2 gives 2^{N-1} full-vehicle items. The PTAS/FPTAS runtimes are polynomial in the item count, so the scheme is not a polynomial-time algorithm. The proof needs a compact encoding: binary splitting of multiplicities, and an argument that only one partial-fill item per edge and mode is needed. Additionally, the proof invokes a PTAS for MKPS with r=|E|+1 constraints, but the cited reference [20] concerns multiobjective knapsack, and multidimensional knapsack with unbounded dimension is not known to admit a PTAS (it generalizes maximum set packing). The claimed approximation schemes are therefore not established as stated.
[Section 3, Theorem 3.2] The reduction as written is internally inconsistent. The MSP decision problem defined in Section 2 requires T(F,L,M) <= a and H(F,L,M) <= b, but the proof states (a,b) := (beta,gamma) and then uses H <= a = beta and T <= b = gamma, so the roles of a and b are swapped relative to the definition. In addition, the cost c1 of the single public transport mode is never specified; for the DiNDP budget beta to map to the MSP budget constraint, one must set c1 = 1. These are fixable, but the reduction is currently ill-defined.
[Section 3, Theorem 3.2 proof, integrality step] The assertion that T(F',L',M') and gamma are integral and hence T(F',L',M') < gamma + 1 implies T(F',L',M') <= gamma is not justified. The rerouted flow F' can be fractional: the original feasible solution is allowed to have fractional flows and fractional modal splits, and no integrality argument is given. Since this integrality is used to close the reduction, the proof needs an explicit argument that an integral feasible solution exists, e.g., by path decomposition with integral demands and non-binding capacities.
[Section 4, Theorem 4.1(a)] The SSUM reduction contains several sign and endpoint errors. The demand should be D(v1, v_{n+1}) = 2 on the last vertex, not D(v1, v_{n-1}); the modal split convention after fixing L is reversed (M(e)=(0,1) means mode 1, so it should be assigned when L(e)_1 = 1, not when L(e)_1 = 0); and the sentence claiming that an edge with L(e)=0 reduces energy should refer to L(e)=1. The intended accounting is recoverable, but as written the reduction does not correctly establish the claimed NP-completeness of fixed-flow MSP.
[Section 4, Theorem 4.2 proof, lower bound] The lower bound H^ := eta * sum_e w(e) F(e) with eta = min_{i=1..m} eta_i is not a valid lower bound when eta_0 < eta, because the all-mode-0 solution has energy H = eta_0 * sum_e w(e) F(e), which could be smaller than H^. The assumption that eta != eta_0 does not address this, since eta_i is energy per vehicle while eta_0 is energy per passenger, so comparing min_{i>=1} eta_i with eta_0 mixes incompatible units. The approximation-factor transformation needs a correct lower bound, for example using min_{i=0..m} eta_i/k_i appropriately or another per-passenger quantity.

minor comments (4)

[Section 4, paragraph before Eq. (3)] In the patch vector expression, the second coordinate of the base point is written as tau_0 * sum_e w(e) F(e), but by Eq. (2) it should be eta_0 * sum_e w(e) F(e).
[Section 4, Theorem 4.3 proof] The vector v_i is defined as (tau_i - tau_0, eta_i/k_i - tau_0); the second entry should be eta_i/k_i - eta_0. Also the preimage of Psi_0 is described by M = 0, but a modal split must satisfy sum_i M_i = 1; this should be the all-mode-0 split.
[Section 4, Theorem 4.1(b) proof] The proof uses the notation 2vmaxW and 2smaxW in the energy computation; these mix v_max/s_max and W/A'. They should be cleaned up for consistency.
[Section 3, Lemma 3.1 proof] In the lower-bound argument for R_{V,U}(G'), the quantity m is undefined; it should be h, the number of U-nodes, matching the previous inequality.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the complexity and approximation proofs reduce from standard external NP-complete problems and cite no load-bearing self-references.

full rationale

No circularity is present in the claimed derivation chain. Theorem 3.2 reduces MSP to DiNDP, and Lemma 3.1 establishes DiNDP NP-completeness by an explicit reduction from X3C, citing the standard undirected network-design result of Johnson, Lenstra, and Rinnooy Kan [13] as an external baseline rather than the authors' own work. Theorem 3.4 reduces from DiSTP, whose NP-completeness is attributed to standard references [15,16]; no target result is assumed as an input. Theorem 4.1 uses reductions from SSUM and UKPS, and the parameter settings are chosen to encode those source instances, not to fit a target outcome. Theorem 4.2 relies on known external PTAS/FPTAS results for KPS and MKPS; the item construction is a gadget encoding, not a fitted input renamed as a prediction. The paper contains no load-bearing self-citations: the central complexity citations are to earlier work by other authors. The reviewer-flagged concern that Theorem 4.2 enumerates items floor(F(e)/k_i) times, which can be exponential in binary-encoded F(e), is a potential correctness or complexity gap in the claimed approximation scheme, but it is not a circularity: the approximation target is not used to define the instance, and no prediction reduces to its own input by construction. Accordingly, the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces no fitted parameters or new physical entities. The reductions rely on standard NP-complete problems and the cited undirected network design result. Two proof-specific assumptions are not justified: integrality of flows in Theorem 3.2 and polynomial size of the constructed approximation instance in Theorem 4.2.

assumptions (6)

domain assumption P ≠ NP
All hardness and inapproximability claims are conditional on this standard computational complexity assumption.
standard math NP-completeness of X3C, ESUM, SSUM, UKPS, STP and DiSTP
Citing [13], [14], [15]; DiSTP NP-hardness is asserted by a sketch reduction from STP.
standard math Undirected Network Design theorem of Johnson, Lenstra, Rinnooy Kan [13]
Lemma 3.1 transfers the undirected structural characterization to the directed case.
ad hoc to paper Feasible MSP flows can be assumed integral in Theorem 3.2
The proof claims T(F',L',M') is integral to infer T ≤ γ from T < γ+1, but multicommodity flows in MSP may be fractional and integrality is not shown.
ad hoc to paper The item set in Theorem 4.2 is polynomial in the input size
F(e)/k_i copies and the enumeration of f can be exponential in the binary encoding; without a compact construction the PTAS/FPTAS argument fails.
domain assumption Mode ordering and cost-per-capacity assumptions in Theorem 4.3
τ0≤τi, monotone slopes τ_i k_i/η_i, and c_m/k_m≤c_i/k_i are explicit assumptions defining the special case.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Complexity Analysis of a Bicriteria Directed Multimodal Transportation Network Design Problem." pith.science (2026). https://pith.science/paper/4Q4FVXNY

@misc{pith2026250707894,
  author       = {Pith},
  title        = {Pith review of: Complexity Analysis of a Bicriteria Directed Multimodal Transportation Network Design Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4Q4FVXNY}},
  note         = {Machine review of arXiv:2507.07894}
}

read the original abstract

In this paper, we address a bicriteria network design problem that arises from practical applications in urban and rural public transportation planning. We establish the problem's complexity and demonstrate inapproximability results, highlighting the inherent difficulties in finding optimal solutions. Additionally, we identify special cases where approximability can be achieved, providing valuable insights for practitioners. Our proofs leverage complexity results related to directed network design problems, an area that has received limited attention in the existing literature. By investigating these complexity results, we aim to fill a critical gap and enhance the understanding of the interplay between bicriteria decision-making and network design challenges.

Figures

Figures reproduced from arXiv: 2507.07894 by the authors.

**Figure 2.** Illustration of the two operations to create a subgraph w [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** Rerouting the flow from mode 0 (in gray) on [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Figures from the paper (5 more)

**Figure 4.** Figure 4: The path graph G with a flow value of 2 between subsequent nodes and edge lengths corresponding to the items in S. need to be chosen in this case to have a value of at least A, which is impossible due to w ≥ 1 for all items. In this case J also decides false, so we ass…

**Figure 5.** Figure 5: The subsegment Ψ of the Pareto frontier of the relaxatio [PITH_FULL_IMAGE:figures/full_fig_p019_5.png]

**Figure 6.** Figure 6: Pareto optimal points ΨL 1 on Ψ and their patches as grey lines. The patches are parallel and their dominated endpoints lie above Ψ0. The shaded grey areas contain the Pareto frontier of all solutions, whose value lie in the area enclosed by the dashed lines and Ψ. Dec…

**Figure 7.** Figure 7: The graph G constructed for the reduction. Any connected subgraph needs to contain the cycles v0 → vi → v ′ i . Adding the reverse edges (v ′ i , vi) then further reduce the routing costs by si . the distance from v ′ i to vi by si and increases the total weight by si…

**Figure 8.** Figure 8: The graph G˜; nodes vi,l are attached to each terminal node vi for l = 1, . . . , hk and a central node q connects two-ways to all nodes, including the Steiner nodes ui , in original G. The pairs denote the weight and routing costs (w(e), d(e)) of each edge. It holds n…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 16 canonical work pages

[20]

Approximating Mult iobjec- tive Knapsack Problems

T. Erlebach, H. Kellerer, and U. Pferschy. “Approximating Mult iobjec- tive Knapsack Problems”. In: Management Science 48.12 (Dec. 2002), pp. 1603–1612. doi: 10.1287/mnsc.48.12.1603.445

work page doi:10.1287/mnsc.48.12.1603.445 2002
[1]

Network Design and Transport ation Planning: Models and Algorithms

T. L. Magnanti and R. T. Wong. “Network Design and Transport ation Planning: Models and Algorithms”. In: Transportation Science 18.1 (Feb. 1984), pp. 1–55. doi: 10.1287/trsc.18.1.1

doi:10.1287/trsc.18.1.1 1984
[2]

R. T. Wong. A Survey of Network Design Problems . Working paper OR 053-76. Massachusetts Institute of Technology, Operations Re search Center, May 1976

work page 1976
[3]

Computational Complex ity of Discrete Optimization Problems

J. K. Lenstra and A. H. G. Rinnooy Kan. “Computational Complex ity of Discrete Optimization Problems”. In: Discrete Optimization I . Ed. by P.L. Hammer, E.L. Johnson, and B.H. Korte. Vol. 4. Annals of Discrete Mathematics. Elsevier, 1979, pp. 121–140. doi: 10 . 1016 / S0167-5060(08)70821-5

work page 1979
[4]

Worst-Case Analysis of Network Design Problem Heu ris- tics

R. T. Wong. “Worst-Case Analysis of Network Design Problem Heu ris- tics”. In: SIAM Journal on Algebraic Discrete Methods 1.1 (1980), pp. 51–63. doi: 10.1137/0601008

work page doi:10.1137/0601008 1980
[5]

T. G. Crainic, M. Gendreau, and B. Gendron. Network Design with Applications to Transportation and Logistics . Springer Books 978-3- 030-64018-7. Springer, Mar. 2021. isbn: 978-3-030-64018-7. doi: 10. 1007/978-3-030-64018-7

work page 2021
[6]

A review of urban transportation networ k design problems

R. Z. Farahani et al. “A review of urban transportation networ k design problems”. In: European journal of operational research 229.2 (2013), pp. 281–302. doi: 10.1016/j.ejor.2013.01.001

doi:10.1016/j.ejor.2013.01.001 2013
[7]

The multiobjective equilibrium network design pr ob- lem revisited: A simulated annealing approach

T. L. Friesz et al. “The multiobjective equilibrium network design pr ob- lem revisited: A simulated annealing approach”. In: European Journal of Operational Research 65.1 (1993), pp. 44–57. issn: 0377-2217. doi: https://doi.org/10.1016/0377-2217(93)90143-B. 24

work page doi:10.1016/0377-2217(93)90143-b 1993

Show all 25 references

[8]

A multi-objective meta- heuristic approach for transit network design and frequency set ting problem in a bus transit system

S. B. Jha, J. K. Jha, and M. K. Tiwari. “A multi-objective meta- heuristic approach for transit network design and frequency set ting problem in a bus transit system”. In: Computers and Industrial Engi- neering 130 (2019), pp. 166–186. issn: 0360-8352. doi: https://doi. org/10...

2019 doi
[9]

Multiobjective design of transportation net- works: Taxonomy and annotation

J. Current and H. Min. “Multiobjective design of transportation net- works: Taxonomy and annotation”. In: European Journal of Opera- tional Research 26.2 (1986), pp. 187–201. issn: 0377-2217. doi: https: //doi.org/10.1016/0377-2217(86)90180-3

1986 doi
[10]

The multi-criteria road network d e- sign problem in an urban area

G. Cantarella and A. Vitetta. “The multi-criteria road network d e- sign problem in an urban area”. In: Transportation 33.6 (Nov. 2006), pp. 567–588. doi: 10.1007/s11116-006-7908-z

2006 doi
[11]

The Bus Rapid Transit investment proble m

R. Hoogervorst et al. “The Bus Rapid Transit investment proble m”. In: Computers and Operations Research 167 (2024), p. 106640. issn: 0305-0548. doi: https://doi.org/10.1016/j.cor.2024.106640

2024
[12]

M. Ehrgott. Multicriteria Optimization . Berlin, Heidelberg: Springer- Verlag, 2005. isbn: 3540213988

2005
[13]

The c om- plexity of the network design problem

D. S. Johnson, J. K. Lenstra, and A. H. G. Rinnooy Kan. “The c om- plexity of the network design problem”. In: Networks 8.4 (1978), pp. 279–

1978
[14]

Reducibility among Combinatorial Problems

R. M. Karp. “Reducibility among Combinatorial Problems”. In: Com- plexity of Computer Computations: Proceedings of a symposi um on the Complexity of Computer Computations . Ed. by Raymond E. Miller, James W. Thatcher, and Jean D. Bohlinger. Boston, MA: Springer US, 1972, pp. 8...

1972 doi
[15]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Math emat- ical Sciences). First Edition. W. H. Freeman, 1979. isbn: 0716710455

1979
[16]

B. H. Korte and J. Vygen. Combinatorial Optimization: Theory and Al- gorithms. New York, NY: Springer-Verlag, 2012. isbn: 9783642244889. doi: 10.1007/978-3-642-24488-9 . 25

2012 doi
[17]

Eﬃcient route planning on public transportation n et- works: A labelling approach

S. Wang et al. “Eﬃcient route planning on public transportation n et- works: A labelling approach”. In: Proceedings of the 2015 ACM SIG- MOD international conference on Management of data . 2015, pp. 967–

2015
[18]

Improved dynamic programming in con- nection with an FPTAS for the knapsack problem

H. Kellerer and U. Pferschy. “Improved dynamic programming in con- nection with an FPTAS for the knapsack problem”. In: Journal of Combinatorial Optimization 8 (2004), pp. 5–11. doi: 10 . 1023 / B : JOCO.0000021934.29833.6b

2004
[19]

A fully polynomial approximation al- gorithm for the 0–1 knapsack problem

M. J. Magazine and O. Oguz. “A fully polynomial approximation al- gorithm for the 0–1 knapsack problem”. In: European Journal of Op- erational Research 8.3 (1981), pp. 270–273. issn: 0377-2217. doi: 10. 1016/0377-2217(81)90175-2

1981
[21]

There is no EPTAS for two-dimensional knapsack

A. Kulik and H. Shachnai. “There is no EPTAS for two-dimensional knapsack”. In: Information Processing Letters 110.16 (2010), pp. 707–

2010
[22]

Algorithm 97: Shortest path

R. W. Floyd. “Algorithm 97: Shortest path”. In: Commun. ACM 5.6 (June 1962), p. 345. issn: 0001-0782. doi: 10.1145/367766.368168. A Appendix Lemma A.1. DiNDP is NP-complete. Proof. DiNDP is in NP, as R can be computed in polynomial time by the Floyd-Warshall algorithm (see [22...

1962
[285]

doi: 10.1002/net.3230080402

doi
[710]

doi: 10.1016/j.ipl.2010.05.031

2010 doi
[982]

doi: 10.1145/2723372.2749456

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [20]

Approximating Mult iobjec- tive Knapsack Problems

T. Erlebach, H. Kellerer, and U. Pferschy. “Approximating Mult iobjec- tive Knapsack Problems”. In: Management Science 48.12 (Dec. 2002), pp. 1603–1612. doi: 10.1287/mnsc.48.12.1603.445

work page doi:10.1287/mnsc.48.12.1603.445 2002

[2] [1]

Network Design and Transport ation Planning: Models and Algorithms

T. L. Magnanti and R. T. Wong. “Network Design and Transport ation Planning: Models and Algorithms”. In: Transportation Science 18.1 (Feb. 1984), pp. 1–55. doi: 10.1287/trsc.18.1.1

doi:10.1287/trsc.18.1.1 1984

[3] [2]

R. T. Wong. A Survey of Network Design Problems . Working paper OR 053-76. Massachusetts Institute of Technology, Operations Re search Center, May 1976

work page 1976

[4] [3]

Computational Complex ity of Discrete Optimization Problems

J. K. Lenstra and A. H. G. Rinnooy Kan. “Computational Complex ity of Discrete Optimization Problems”. In: Discrete Optimization I . Ed. by P.L. Hammer, E.L. Johnson, and B.H. Korte. Vol. 4. Annals of Discrete Mathematics. Elsevier, 1979, pp. 121–140. doi: 10 . 1016 / S0167-5060(08)70821-5

work page 1979

[5] [4]

Worst-Case Analysis of Network Design Problem Heu ris- tics

R. T. Wong. “Worst-Case Analysis of Network Design Problem Heu ris- tics”. In: SIAM Journal on Algebraic Discrete Methods 1.1 (1980), pp. 51–63. doi: 10.1137/0601008

work page doi:10.1137/0601008 1980

[6] [5]

T. G. Crainic, M. Gendreau, and B. Gendron. Network Design with Applications to Transportation and Logistics . Springer Books 978-3- 030-64018-7. Springer, Mar. 2021. isbn: 978-3-030-64018-7. doi: 10. 1007/978-3-030-64018-7

work page 2021

[7] [6]

A review of urban transportation networ k design problems

R. Z. Farahani et al. “A review of urban transportation networ k design problems”. In: European journal of operational research 229.2 (2013), pp. 281–302. doi: 10.1016/j.ejor.2013.01.001

doi:10.1016/j.ejor.2013.01.001 2013

[8] [7]

The multiobjective equilibrium network design pr ob- lem revisited: A simulated annealing approach

T. L. Friesz et al. “The multiobjective equilibrium network design pr ob- lem revisited: A simulated annealing approach”. In: European Journal of Operational Research 65.1 (1993), pp. 44–57. issn: 0377-2217. doi: https://doi.org/10.1016/0377-2217(93)90143-B. 24

work page doi:10.1016/0377-2217(93)90143-b 1993