{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T01:25:08Z","timestamp":1777339508757,"version":"3.51.4"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,2,12]],"date-time":"2009-02-12T00:00:00Z","timestamp":1234396800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,8]]},"DOI":"10.1007\/s00224-009-9191-9","type":"journal-article","created":{"date-parts":[[2009,2,11]],"date-time":"2009-02-11T18:14:28Z","timestamp":1234376068000},"page":"405-432","source":"Crossref","is-referenced-by-count":17,"title":["Computing Nash Equilibria for Scheduling on\u00a0Restricted Parallel Links"],"prefix":"10.1007","volume":"47","author":[{"given":"Martin","family":"Gairing","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"L\u00fccking","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marios","family":"Mavronicolas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Burkhard","family":"Monien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,2,12]]},"reference":[{"key":"9191_CR1","volume-title":"Network Flows: Theory, Algorithms and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, New York (1993)"},{"issue":"2\u20133","key":"9191_CR2","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.tcs.2006.05.010","volume":"361","author":"B. Awerbuch","year":"2006","unstructured":"Awerbuch, B., Azar, Y., Richter, Y., Tsur, D.: Tradeoffs in worst-case equilibria. Theor. Comput. Sci. 361(2\u20133), 200\u2013209 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9191_CR3","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player Nash equilibrium. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 261\u2013272 (2006)","DOI":"10.1109\/FOCS.2006.69"},{"key":"9191_CR4","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 71\u201378 (2006)","DOI":"10.1145\/1132516.1132527"},{"key":"9191_CR5","first-page":"1277","volume":"11","author":"E.A. Dinits","year":"1970","unstructured":"Dinits, E.A.: Algorithm for solution of a problem of maximum flow in a network with power estimation. Sov. Math. Dokl. 11, 1277\u20131280 (1970)","journal-title":"Sov. Math. Dokl."},{"issue":"1","key":"9191_CR6","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s004930050043","volume":"19","author":"Y. Dinitz","year":"1999","unstructured":"Dinitz, Y., Garg, N., Goemans, M.X.: On the single-source unsplittable flow problem. Combinatorica 19(1), 17\u201341 (1999)","journal-title":"Combinatorica"},{"key":"9191_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1007\/3-540-45061-0_42","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages, and Programming","author":"R. Feldmann","year":"2003","unstructured":"Feldmann, R., Gairing, M., L\u00fccking, T., Monien, B., Rode, M.: Nashification and the coordination ratio for a selfish routing game. In: Proceedings of the 30th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 2719, pp. 514\u2013526. Springer, Berlin (2003)"},{"key":"9191_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/3-540-45465-9_12","volume-title":"Proceedings of the 29th International Colloquium on Automata, Languages, and Programming","author":"D. Fotakis","year":"2002","unstructured":"Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., Spirakis, P.: The structure and complexity of Nash equilibria for a selfish routing game. In: Proceedings of the 29th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 2380, pp. 123\u2013134. Springer, Berlin (2002)"},{"issue":"1\u20132","key":"9191_CR9","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.tcs.2005.05.011","volume":"343","author":"M. Gairing","year":"2005","unstructured":"Gairing, M., L\u00fccking, T., Mavronicolas, M., Monien, B., Spirakis, P.: Structure and complexity of extreme Nash equilibria. Theor. Comput. Sci. 343(1\u20132), 133\u2013157 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9191_CR10","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1142\/S0129626406002514","volume":"16","author":"M. Gairing","year":"2006","unstructured":"Gairing, M., L\u00fccking, T., Mavronicolas, M., Monien, B.: The price of anarchy for restricted parallel links. Parallel Process. Lett. 16(1), 117\u2013131 (2006)","journal-title":"Parallel Process. Lett."},{"issue":"1\u20132","key":"9191_CR11","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.tcs.2007.02.056","volume":"380","author":"M. Gairing","year":"2007","unstructured":"Gairing, M., Monien, B., Woclaw, A.: A faster combinatorial approximation algorithm for scheduling unrelated parallel machines. Theor. Comput. Sci. 380(1\u20132), 87\u201399 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9191_CR12","unstructured":"Goldberg, A.V.: Efficient graph algorithms for sequential and parallel computers. Ph.D. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology (1987)"},{"issue":"4","key":"9191_CR13","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. J. ACM 35(4), 921\u2013940 (1988)","journal-title":"J. ACM"},{"issue":"2","key":"9191_CR14","first-page":"317","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J.\u00a0ACM 23(2), 317\u2013327 (1976)","journal-title":"J.\u00a0ACM"},{"key":"9191_CR15","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Single-source unsplittable flow. In: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pp. 68\u201377 (1996)","DOI":"10.1109\/SFCS.1996.548465"},{"issue":"3","key":"9191_CR16","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1137\/S0097539799355314","volume":"31","author":"S.G. Kolliopoulos","year":"2002","unstructured":"Kolliopoulos, S.G., Stein, C.: Approximation algorithms for single-source unsplittable flow. SIAM J. Comput. 31(3), 919\u2013946 (2002)","journal-title":"SIAM J. Comput."},{"key":"9191_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/3-540-49116-3_38","volume-title":"Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science","author":"E. Koutsoupias","year":"1999","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol.\u00a01563, pp. 404\u2013413. Springer, Berlin (1999)"},{"issue":"3","key":"9191_CR18","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J.K. Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(3), 259\u2013271 (1990)","journal-title":"Math. Program."},{"key":"9191_CR19","unstructured":"McKelvey, R.D., McLennan, A.: Computation of equilibria in finite games. In: Amman,\u00a0H., Kendrick,\u00a0D., Rust,\u00a0J. (eds.) Handbook of Computational Economics, vol.\u00a01, pp. 87\u2013142 (1996). Chap.\u00a02"},{"issue":"1","key":"9191_CR20","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1006\/game.1996.0027","volume":"13","author":"I. Milchtaich","year":"1996","unstructured":"Milchtaich, I.: Congestion games with player-specific payoff functions. Games Econ. Behav. 13(1), 111\u2013124 (1996)","journal-title":"Games Econ. Behav."},{"key":"9191_CR21","doi-asserted-by":"crossref","unstructured":"Nash, J.F.: Equilibrium points in n-person games. In: Proceedings of the National Academy of Sciences of the United States of America, vol. 36, pp. 48\u201349 (1950)","DOI":"10.1073\/pnas.36.1.48"},{"issue":"2","key":"9191_CR22","doi-asserted-by":"crossref","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J.F. Nash","year":"1951","unstructured":"Nash, J.F.: Non-cooperative games. Ann. Math. 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"9191_CR23","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: Algorithms, games and the Internet. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 749\u2013753 (2001)","DOI":"10.1145\/380752.380883"},{"issue":"2","key":"9191_CR24","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.orl.2004.05.004","volume":"33","author":"E.V. Shchepin","year":"2005","unstructured":"Shchepin, E.V., Vakhania, N.: An optimal rounding gives a better approximation for scheduling unrelated machines. Oper. Res. Lett. 33(2), 127\u2013133 (2005)","journal-title":"Oper. Res. Lett."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9191-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9191-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9191-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:37Z","timestamp":1558698697000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9191-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,12]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["9191"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9191-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,12]]}}}