×

zbMATH — the first resource for mathematics

New complexity results and algorithms for the minimum tollbooth problem. (English) Zbl 1404.91041
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 89-103 (2015).
Summary: 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.
For the entire collection see [Zbl 1326.68026].

MSC:
91A43 Games involving graphs
91A13 Games with infinitely many players (MSC2010)
90B20 Traffic problems in operations research
91-04 Software, source code, etc. for problems pertaining to game theory, economics, and finance
05C90 Applications of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bai, L., Hearn, D.W., Lawphongpanich, S.: A heuristic method for the minimum toll booth problem. J. Global Optim. 48(4), 533–548 (2010) · Zbl 1206.90172 · doi:10.1007/s10898-010-9527-7
[2] Bai, L., Rubin, P.A.: Combinatorial benders cuts for the minimum tollbooth problem. Oper. Res. 57(6), 1510–1522 (2009) · Zbl 1226.90122 · doi:10.1287/opre.1090.0694
[3] Bai, L., Stamps, M.T., Harwood, R.C., Kollmann, C.J., Seminary, C.: An evolutionary method for the minimum toll booth problem: The methodology. Acad. Info. Manage. Sci. J. 11(2), 33 (2008)
[4] Baier, G., Erlebach, T., Hall, A., Köhler, E., Kolman, P., Pangrác, O., Schilling, H., Skutella, M.: Length-bounded cuts and flows. ACM Trans. Algorithms (TALG) 7(1), 4 (2010) · Zbl 1295.68119
[5] Basu, S., Lianeas, T., Nikolova, E.: New complexity results and algorithms for the minimum tollbooth problem (2015). http://arxiv.org/abs/1509.07260 · Zbl 1404.91041
[6] Beckmann, M., McGuire, C., Weinstein, C.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
[7] Bergendorff, P., Hearn, D.W., Ramana, M.V.: Congestion toll pricing of traffic networks. In: Pardalos, P.M., Heam, D.W., Hager, W.W. (eds.) Network Optimization. LNEMS, vol. 450, pp. 51–71. Springer, Heidelberg (1997) · Zbl 0878.90040 · doi:10.1007/978-3-642-59179-2_4
[8] Buriol, L.S., Hirsch, M.J., Pardalos, P.M., Querido, T., Resende, M.G., Ritt, M.: A biased random-key genetic algorithm for road congestion minimization. Optim. Lett. 4(4), 619–633 (2010) · Zbl 1202.90025 · doi:10.1007/s11590-010-0226-6
[9] Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439–485 (2005) · Zbl 1084.68051 · doi:10.4007/annals.2005.162.439
[10] Garey, M.R., Johnson, D.S.: Computers and intractability, vol. 29. W.H. Freeman (2002)
[11] Harks, T., Schäfer, G., Sieg, M.: Computing flow-inducing network tolls. Technical report, 36–2008, Institut für Mathematik, Technische Universität Berlin, Germany (2008)
[12] Hearn, D.W., Ramana, M.V.: Solving congestion toll pricing models. In: Marcotte, P., Nguyen, S., (eds.) Equilibrium and Advanced Transportation Modelling. Centre for Research on Transportation, pp. 109–124. Springer, New York (1998) · Zbl 1067.90508 · doi:10.1007/978-1-4615-5757-9_6
[13] Hoefer, Martin, Olbrich, Lars, Skopalik, Alexander: Taxing subnetworks. In: Papadimitriou, Christos, Zhang, Shuzhong (eds.) WINE 2008. LNCS, vol. 5385, pp. 286–294. Springer, Heidelberg (2008) · Zbl 05496542 · doi:10.1007/978-3-540-92185-1_35
[14] Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT Press, Cambridge (2005) · Zbl 1318.68065
[15] Stefanello, F., Buriol, L., Hirsch, M., Pardalos, P., Querido, T., Resende, M., Ritt, M.: On the minimization of traffic congestion in road networks with tolls. Ann. Oper. Res., 1–21 (2013) · Zbl 1357.90032
[16] The Centre for Economics and Business Research: The future economic and environmental costs of gridlock in 2030. Technical report. INRIX, Inc. (2014)
[17] Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, pp. 1–12. ACM (1979) · Zbl 0478.68065 · doi:10.1145/800135.804393
[18] Wardrop, J.G.: Road Paper. Some Theoretical Aspects of Road Traffic Research. In: ICE Proceedings: Engineering Divisions, vol. 1, pp. 325–362. Thomas Telford (1952)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.