English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We revisit a classical problem in transportation, known as the continuous(bilevel) network design problem, CNDP for short. We are given a graph forwhich the latency of each edge depends on the ratio of the edge flow and thecapacity installed. The goal is to find an optimal investment in edgecapacities so as to minimize the sum of the routing cost of the induced Wardropequilibrium and the investment cost. While this problem is considered aschallenging in the literature, its complexity status was still unknown. Weclose this gap showing that CNDP is strongly NP-complete and APX-hard, both ondirected and undirected networks and even for instances with affine latencies.  As for the approximation of the problem, we first provide a detailed analysisfor a heuristic studied by Marcotte for the special case of monomial latencyfunctions (Mathematical Programming, Vol.~34, 1986). Specifically, we derive aclosed form expression of its approximation guarantee for arbitrary sets S ofallowed latency functions. Second, we propose a different approximationalgorithm and show that it has the same approximation guarantee. As our final-- and arguably most interesting -- result regarding approximation, we showthat using the better of the two approximation algorithms results in a strictlyimproved approximation guarantee for which we give a closed form expression.For affine latencies, e.g., this algorithm achieves a 1.195-approximation whichimproves on the 5/4 that has been shown before by Marcotte. We finally discussthe case of hard budget constraints on the capacity investment.

Complexity and Approximation of the Continuous Network Design Problem