{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:38:00Z","timestamp":1758274680159},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,6,28]],"date-time":"2016-06-28T00:00:00Z","timestamp":1467072000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s00453-016-0175-2","type":"journal-article","created":{"date-parts":[[2016,6,28]],"date-time":"2016-06-28T11:17:45Z","timestamp":1467112665000},"page":"788-818","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Resolving Braess\u2019s Paradox in Random Networks"],"prefix":"10.1007","volume":"78","author":[{"given":"Dimitris","family":"Fotakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexis C.","family":"Kaporis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thanasis","family":"Lianeas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,28]]},"reference":[{"key":"175_CR1","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/0024-3795(94)90357-3","volume":"99","author":"I Alth\u00f6fer","year":"1994","unstructured":"Alth\u00f6fer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebra Appl. 99, 339\u2013355 (1994)","journal-title":"Linear Algebra Appl."},{"key":"175_CR2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs, 2nd Edition Cambridge Studies in Advanced Mathematics","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, 2nd Edition Cambridge Studies in Advanced Mathematics, vol. 3. Cambridge University Press, Cambridge (2001)"},{"key":"175_CR3","first-page":"258","volume":"12","author":"D Braess","year":"1968","unstructured":"Braess, D.: \u00dcber ein paradox aus der Verkehrsplanung. Unternehmensforschung 12, 258\u2013268 (1968)","journal-title":"Unternehmensforschung"},{"key":"175_CR4","first-page":"331","volume":"1","author":"P Cheeseman","year":"1991","unstructured":"Cheeseman, P., Kanefsky, B., Taylor, W.: Where the really hard problems are. IJCAI 1, 331\u2013337 (1991)","journal-title":"IJCAI"},{"key":"175_CR5","doi-asserted-by":"crossref","unstructured":"Chung, F., Young, S.J.: Braess\u2019s paradox in large sparse graphs. In: Proceedings of the 6th Workshop on Internet and Network Economics (WINE\u00a0\u201910), LNCS, vol. 6484, pp. 194\u2013208 (2010)","DOI":"10.1007\/978-3-642-17572-5_16"},{"issue":"4","key":"175_CR6","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1002\/rsa.20457","volume":"41","author":"F Chung","year":"2012","unstructured":"Chung, F., Young, S.J., Zhao, W.: Braess\u2019s paradox in expanders. Random Struct. Algorithms 41(4), 451\u2013468 (2012)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"175_CR7","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1016\/j.jcss.2005.09.010","volume":"72","author":"R Cole","year":"2006","unstructured":"Cole, R., Dodis, Y., Roughgarden, T.: How much can taxes help selfish routing? J. Comput. Syst. Sci. 72(3), 444\u2013467 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"175_CR8","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"RJ Duffin","year":"1965","unstructured":"Duffin, R.J.: Topology of serries-parallel networks. J. Math. Anal. Appl. 10, 303\u2013318 (1965)","journal-title":"J. Math. Anal. Appl."},{"key":"175_CR9","first-page":"17","volume":"5","author":"P Erdos","year":"1960","unstructured":"Erdos, P., Renyi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17\u201361 (1960)","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"175_CR10","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.tcs.2012.04.033","volume":"448","author":"D Fotakis","year":"2012","unstructured":"Fotakis, D., Kaporis, A.C., Spirakis, P.G.: Efficient methods for selfish network design. Theor. Comput. Sci. 448, 9\u201320 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"175_CR11","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0304-3975(01)00158-X","volume":"265","author":"J Franco","year":"2001","unstructured":"Franco, J.: Results related to threshold phenomena research in satisfiability: lower bounds. Theor. Comput. Sci. 265, 147\u2013157 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"175_CR12","doi-asserted-by":"crossref","unstructured":"Friedman, E.: Genericity and congestion control in selfish routing. In: 43rd IEEE Conference on Decision and Control, pp. 4667\u20134672 (2004)","DOI":"10.1109\/CDC.2004.1429524"},{"issue":"6","key":"175_CR13","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T Hagerup","year":"1990","unstructured":"Hagerup, T., R\u00fcb, C.: A guided tour of Chernoff bounds. Inf. Process. Lett. 33(6), 305\u2013308 (1990)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"175_CR14","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0196-6774(84)90032-4","volume":"5","author":"D Johnson","year":"1984","unstructured":"Johnson, D.: The NP-completeness column: an ongoing guide. J. Algorithms 5(2), 284\u2013299 (1984)","journal-title":"J. Algorithms"},{"issue":"6","key":"175_CR15","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1287\/opre.37.6.865","volume":"37","author":"D Johnson","year":"1989","unstructured":"Johnson, D., Aragon, C., McGeoch, L., Shevon, C.: Optimization by simulated annealing: an experimental evaluation. Oper. Res. 37(6), 865\u2013892 (1989)","journal-title":"Oper. Res."},{"issue":"2","key":"175_CR16","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1145\/5657.5658","volume":"29","author":"R Karp","year":"1989","unstructured":"Karp, R.: Combinatorics, complexity, and randomness (turing award lecture). Commun. ACM 29(2), 98\u2013109 (1989)","journal-title":"Commun. ACM"},{"key":"175_CR17","volume-title":"The Mathematics of Traffic in Networks","author":"F Kelly","year":"2008","unstructured":"Kelly, F.: The Princeton companion to mathematics. In: Gowers, T., Green, J., Leader, I. (eds.) The Mathematics of Traffic in Networks. Princeton University Press, Princeton (2008)"},{"key":"175_CR18","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S Kirkpatrick","year":"1994","unstructured":"Kirkpatrick, S., Selman, B.: Critical behavior in the satisfiability of random Boolean expressions. Science 264, 1297\u20131301 (1994)","journal-title":"Science"},{"issue":"4","key":"175_CR19","doi-asserted-by":"crossref","first-page":"1667","DOI":"10.1137\/090769600","volume":"25","author":"HC Lin","year":"2011","unstructured":"Lin, H.C., Roughgarden, T., Tardos, \u00c9., Walkover, A.: Stronger bounds on Braess\u2019s paradox and the maximum latency of selfish routing. SIAM J. Discrete Math. 25(4), 1667\u20131686 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"175_CR20","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proceedings of the 4th ACM Conference on Electronic Commerce (EC\u00a0\u201903), pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"key":"175_CR21","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Young, N.E.: Simple strategies for large zero-sum games with applications to complexity theory. In: Proceedings of the 26th ACM symposium on theory of computing (STOC\u00a0\u201994), pp. 734\u2013740 (1994)","DOI":"10.1145\/195058.195447"},{"key":"175_CR22","doi-asserted-by":"crossref","unstructured":"M\u00e9zard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science 297, 812\u2013815 (2002)","DOI":"10.1126\/science.1073287"},{"key":"175_CR23","unstructured":"Mitchell, D., Selman, B., Levesque, H.: Hard and easy distribution of SAT problems. In: Proceeings of 10th National Conference on Artificial Intelligence (AAAI \u201992), pp. 459\u2013465"},{"key":"175_CR24","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.geb.2005.09.005","volume":"57","author":"I Milchtaich","year":"2006","unstructured":"Milchtaich, I.: Network topology and the efficiency of equilibrium. Games Econ. Behav. 57, 321\u2013346 (2006)","journal-title":"Games Econ. Behav."},{"key":"175_CR25","unstructured":"Morris, P.: The breakthrough method for escaping local minima. AAAI 6, 40-45 (1993)"},{"key":"175_CR26","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/0041-1647(70)90196-6","volume":"4","author":"JD Murchland","year":"1970","unstructured":"Murchland, J.D.: Braess\u2019s paradox of traffic flow. Transp. Res. 4, 391\u2013394 (1970)","journal-title":"Transp. Res."},{"issue":"4","key":"175_CR27","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1287\/trsc.1050.0126","volume":"39","author":"A Nagurney","year":"2005","unstructured":"Nagurney, A., Boyce, D.: Preface to \u201con a paradox of traffic planning\u201d. Transp. Sci. 39(4), 443\u2013445 (2005)","journal-title":"Transp. Sci."},{"issue":"3","key":"175_CR28","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/S0191-2615(96)00024-0","volume":"31","author":"EI Pas","year":"1997","unstructured":"Pas, E.I., Principio, S.L.: Braess\u2019s paradox: some new insights. Transp. Res. Part B 31(3), 265\u2013276 (1997)","journal-title":"Transp. Res. Part B"},{"key":"175_CR29","volume-title":"The Traffic Assignment Problem\u2014Models and Methods","author":"M Patriksson","year":"1991","unstructured":"Patriksson, M.: The Traffic Assignment Problem\u2014Models and Methods. Link\u00f6ping Institute of Technology, Link\u00f6ping (1991)"},{"key":"175_CR30","unstructured":"Roughgarden, T.: Selfish Routing. Ph.D dissertation, Cornell Univ., USA, May (2002). http:\/\/theory.stanford.edu\/~tim\/"},{"issue":"2","key":"175_CR31","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1137\/S0097539701397059","volume":"33","author":"T Roughgarden","year":"2004","unstructured":"Roughgarden, T.: Stackelberg scheduling strategies. SIAM J. Comput. 33(2), 332\u2013350 (2004)","journal-title":"SIAM J. Comput."},{"key":"175_CR32","doi-asserted-by":"crossref","unstructured":"Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT press, Cambridge, MA (2005)","DOI":"10.21236\/ADA637949"},{"issue":"5","key":"175_CR33","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1016\/j.jcss.2005.05.009","volume":"72","author":"T Roughgarden","year":"2006","unstructured":"Roughgarden, T.: On the severity of braess\u2019s paradox: designing networks for selfish users is hard. J. Comput. Syst. Sci. 72(5), 922\u2013953 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"175_CR34","unstructured":"Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing. DIMACS 26, 521\u2013532 (1993)"},{"issue":"3","key":"175_CR35","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1287\/trsc.17.3.301","volume":"17","author":"R Steinberg","year":"1983","unstructured":"Steinberg, R., Zangwill, W.I.: The prevalence of Braess\u2019 paradox. Transp. Sci. 17(3), 301\u2013318 (1983)","journal-title":"Transp. Sci."},{"issue":"4","key":"175_CR36","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1002\/rsa.20325","volume":"37","author":"G Valiant","year":"2010","unstructured":"Valiant, G., Roughgarden, T.: Braess\u2019s paradox in large random graphs. Random Struct. Algorithms 37(4), 495\u2013515 (2010)","journal-title":"Random Struct. Algorithms"},{"key":"175_CR37","doi-asserted-by":"crossref","unstructured":"V\u00e9gh, L.A.: Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. In: Proceedings of the 44th ACM Symposium on Theory of Computing (STOC\u00a0\u201912), pp. 27\u201340 (2012)","DOI":"10.1145\/2213977.2213981"},{"key":"175_CR38","unstructured":"International Competition and Symposium on Satisfiability Testing, Beijing \u201996, Beijing, China, March 15\u201317 (1996)"},{"key":"175_CR39","unstructured":"2nd Dimacs Implementation Challenge. In: Johnson, D., Trick, M. (eds.) Dimacs Series in Discrete Mathematics and TCS, 26(4), AMS (1996). http:\/\/dimacs.rutgers.edu\/Volumes\/Vol26.html"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0175-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0175-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0175-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0175-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,10]],"date-time":"2019-09-10T05:15:21Z","timestamp":1568092521000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0175-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,28]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["175"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0175-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,28]]}}}