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

The inefficiency of the Wardrop equilibrium of nonatomic routing games can beeliminated by placing tolls on the edges of a network so that the sociallyoptimal flow is induced as an equilibrium flow. A solution where the minimumnumber of edges are tolled may be preferable over others due to its ease ofimplementation in real networks. In this paper we consider the minimumtollbooth (MINTB) problem, which seeks social optimum inducing tolls withminimum support. We prove for single commodity networks with linear latenciesthat the problem is NP-hard to approximate within a factor of $1.1377$ througha reduction from the minimum vertex cover problem. Insights from network designmotivate us to formulate a new variation of the problem where, in addition toplacing tolls, it is allowed to remove unused edges by the social optimum. Weprove that this new problem remains NP-hard even for single commodity networkswith linear latencies, using a reduction from the partition problem. On thepositive side, we give the first exact polynomial solution to the MINTB problemin an important class of graphs---series-parallel graphs. Our algorithm solvesMINTB by first tabulating the candidate solutions for subgraphs of theseries-parallel network and then combining them optimally.

New Complexity Results and Algorithms for the Minimum Tollbooth Problem