New complexity results and algorithms for the minimum tollbooth problem

DOI10.1007/978-3-662-48995-6_7MaRDI QIDQ3460779zbMATH OpenOpenAlexFDO

Authors Soumya Basu, Thanasis Lianeas, E. Nikolova

Publication date 8 January 2016

Published in Web and Internet Economics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/1509.07260

zbMATH Keywords

algorithm complexityminimum tollbooth problemnonatomic routing gamesWardrop equilibrium

Mathematics Subject Classification ID

Applications of graph theory (05C90) Traffic problems in operations research (90B20) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Games with infinitely many players (91A07) Games involving graphs (91A43)

Abstract: The inefficiency of the Wardrop equilibrium of nonatomic routing games can be eliminated by placing tolls on the edges of a network so that the socially optimal flow is induced as an equilibrium flow. A solution where the minimum number of edges are tolled may be preferable over others due to its ease of implementation in real networks. In this paper we consider the minimum tollbooth (MINTB) problem, which seeks social optimum inducing tolls with minimum support. We prove for single commodity networks with linear latencies that the problem is NP-hard to approximate within a factor of $1.1377$ through a reduction from the minimum vertex cover problem. Insights from network design motivate us to formulate a new variation of the problem where, in addition to placing tolls, it is allowed to remove unused edges by the social optimum. We prove that this new problem remains NP-hard even for single commodity networks with linear latencies, using a reduction from the partition problem. On the positive side, we give the first exact polynomial solution to the MINTB problem in an important class of graphs---series-parallel graphs. Our algorithm solves MINTB by first tabulating the candidate solutions for subgraphs of the series-parallel network and then combining them optimally.

Recommendations

• The minimum tollbooth problem in atomic network congestion games with unsplittable flows
• Automata, Languages and Programming
• Linear tolls suffice: new bounds and algorithms for tolls in single source networks
• Computing network tolls with support constraints
• Demand-independent optimal tolls

Cites work

• A biased random-key genetic algorithm for road congestion minimization
• A heuristic method for the minimum toll booth problem
• Combinatorial Benders cuts for the minimum tollbooth problem
• scientific article; zbMATH DE number 1086905 (Why is no real title available?)
• scientific article; zbMATH DE number 1488061 (Why is no real title available?)
• scientific article; zbMATH DE number 6469241 (Why is no real title available?)
• Length-bounded cuts and flows
• New complexity results and algorithms for the minimum tollbooth problem
• On the hardness of approximating minimum vertex cover
• On the minimization of traffic congestion in road networks with tolls
• The Recognition of Series Parallel Digraphs

Cited in

(2)

• The minimum tollbooth problem in atomic network congestion games with unsplittable flows
• New complexity results and algorithms for the minimum tollbooth problem

This page was built for publication: New complexity results and algorithms for the minimum tollbooth problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460779)