{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:34Z","timestamp":1759639054229,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":72,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_1","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"1-17","source":"Crossref","is-referenced-by-count":5,"title":["Local Search: Simple, Successful, But Sometimes Sluggish"],"prefix":"10.1007","author":[{"given":"Burkhard","family":"Monien","sequence":"first","affiliation":[]},{"given":"Dominic","family":"Dumrauf","sequence":"additional","affiliation":[]},{"given":"Tobias","family":"Tscheuschner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","series-title":"Monographs in Theoretical Computer Science. An EATCS Series","volume-title":"Theoretical Aspects of Local Search","author":"E. Aarts","year":"2007","unstructured":"Aarts, E., Korst, J., Michiels, W.: Theoretical Aspects of Local Search. Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag New York, Inc., Secaucus (2007)"},{"volume-title":"Local Search in Combinatorial Optimization","year":"1997","key":"1_CR2","unstructured":"Aarts, E., Lenstra, J.K. (eds.): Local Search in Combinatorial Optimization. John Wiley & Sons, Inc., New York (1997)"},{"issue":"6","key":"1_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1455248.1455249","volume":"55","author":"H. Ackermann","year":"2008","unstructured":"Ackermann, H., R\u00f6glin, H., V\u00f6cking, B.: On the impact of combinatorial structure on congestion games. J. ACM\u00a055(6), 1\u201322 (2008)","journal-title":"J. ACM"},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-540-77105-0_47","volume-title":"Internet and Network Economics","author":"H. Ackermann","year":"2007","unstructured":"Ackermann, H., Skopalik, A.: On the complexity of pure nash equilibria in player-specific network congestion games. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol.\u00a04858, pp. 419\u2013430. Springer, Heidelberg (2007)"},{"issue":"4","key":"1_CR5","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1016\/0885-064X(87)90007-0","volume":"3","author":"I. Adler","year":"1987","unstructured":"Adler, I., Karp, R.M., Shamir, R.: A simplex variant solving an times linear program in (min(m2, d 2)expected number of pivot steps. J. Complexity\u00a03(4), 372\u2013387 (1987)","journal-title":"J. Complexity"},{"issue":"3","key":"1_CR6","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1016\/j.ejor.2006.12.063","volume":"191","author":"E. Alekseeva","year":"2008","unstructured":"Alekseeva, E., Kochetov, Y., Plyasunov, A.: Complexity of local search for the p-median problem. European Journal of Operational Research\u00a0191(3), 736\u2013752 (2008)","journal-title":"European Journal of Operational Research"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: k-means has polynomial smoothed complexity. CoRR, abs\/0904.1113 (2009)","DOI":"10.1109\/FOCS.2009.14"},{"volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","year":"2004","key":"1_CR8","unstructured":"Babai, L. (ed.): Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16. ACM, New York (2004)"},{"issue":"1","key":"1_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1287\/opre.50.1.3.17780","volume":"50","author":"R.E. Bixby","year":"2002","unstructured":"Bixby, R.E.: Solving real-world linear programs: A decade and more of progress. Operations Research\u00a050(1), 3\u201315 (2002)","journal-title":"Operations Research"},{"key":"1_CR10","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1090\/conm\/114\/1097863","volume":"114","author":"K.H. Borgwardt","year":"1990","unstructured":"Borgwardt, K.H.: Probabilistic analysis of simplex algorithms. Contemporary Mathematics\u00a0114, 21\u201334 (1990)","journal-title":"Contemporary Mathematics"},{"issue":"3","key":"1_CR11","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.jcss.2008.09.001","volume":"75","author":"F. Brandt","year":"2009","unstructured":"Brandt, F., Fischer, F., Holzer, M.: Symmetries and the complexity of pure nash equilibrium. Journal of Computer and System Sciences\u00a075(3), 163\u2013177 (2009)","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"1_CR12","doi-asserted-by":"publisher","first-page":"1998","DOI":"10.1137\/S0097539793251244","volume":"28","author":"B. Chandra","year":"1999","unstructured":"Chandra, B., Karloff, H.J., Tovey, C.A.: New results on the old k-opt algorithm for the traveling salesman problem. SIAM J. Comput.\u00a028(6), 1998\u20132029 (1999)","journal-title":"SIAM J. Comput."},{"issue":"1-4","key":"1_CR13","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10472-004-9419-y","volume":"43","author":"P. Chapdelaine","year":"2005","unstructured":"Chapdelaine, P., Creignou, N.: The complexity of boolean constraint satisfaction local search problems. Annals of Mathematics and Artificial Intelligence\u00a043(1-4), 51\u201363 (2005)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player nash equilibria. J. ACM\u00a056(3) (2009)","DOI":"10.1145\/1516512.1516516"},{"key":"1_CR15","unstructured":"Chien, S., Sinclair, A.: Convergence to approximate nash equilibria in congestion games. Games and Economic Behavior (2009), (in press, accepted manuscript)"},{"key":"1_CR16","unstructured":"Danzig, G.: Programming in linear structure. Technical report, U.S. Air Force Comptroller, USAF, Washington, D.C. (1948)"},{"issue":"1","key":"1_CR17","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C. Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a nash equilibrium. SIAM J. Comput.\u00a039(1), 195\u2013259 (2009)","journal-title":"SIAM J. Comput."},{"key":"1_CR18","volume-title":"Pattern Classification","author":"R.O. Duda","year":"2000","unstructured":"Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification. John Wiley & Sons, Inc., Chichester (2000)"},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/978-3-540-92185-1_18","volume-title":"WINE","author":"D. Dumrauf","year":"2008","unstructured":"Dumrauf, D., Monien, B.: On the road to $\\mathcal{PLS}$ -completeness: 8 agents in a singleton congestion game. In: Papadimitriou, C.H., Zhang, S. (eds.) WINE. LNCS, vol.\u00a05385, pp. 94\u2013108. Springer, Heidelberg (2008)"},{"issue":"4","key":"1_CR20","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1287\/moor.1080.0322","volume":"33","author":"J. Dunkel","year":"2008","unstructured":"Dunkel, J., Schulz, A.S.: On the complexity of pure-strategy nash equilibria in congestion and local-effect games. Math. Oper. Res.\u00a033(4), 851\u2013868 (2008)","journal-title":"Math. Oper. Res."},{"key":"1_CR21","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-opt algorithm for the tsp. Electronic Colloquium on Computational Complexity (ECCC)\u00a013(092) (2006)"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure nash equilibria. In: Babai [8], pp. 604\u2013612","DOI":"10.1145\/1007352.1007445"},{"key":"1_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/3-540-45061-0_42","volume-title":"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: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 514\u2013526. Springer, Heidelberg (2003)"},{"key":"1_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/3-540-45465-9_12","volume-title":"Automata, Languages and Programming","author":"D. Fotakis","year":"2002","unstructured":"Fotakis, D., Kontogiannis, S.C., Koutsoupias, E., Mavronicolas, M., Spirakis, P.G.: The structure and complexity of nash equilibria for a selfish routing game. In: Widmayer, P., Triguero Ruiz, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 123\u2013134. Springer, Heidelberg (2002)"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Gairing, M., L\u00fccking, T., Mavronicolas, M., Monien, B.: Computing nash equilibria for scheduling on restricted parallel links. In: Babai [8], pp. 613\u2013622","DOI":"10.1145\/1007352.1007446"},{"key":"1_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/11786986_44","volume-title":"Automata, Languages and Programming","author":"M. Gairing","year":"2006","unstructured":"Gairing, M., Monien, B., Tiemann, K.: Routing (un-) splittable flow in games with player-specific linear latency functions. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 501\u2013512. Springer, Heidelberg (2006)"},{"key":"1_CR27","series-title":"Mathematical Sciences Series","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. Mathematical Sciences Series. W. H. Freeman & Co., New York (1990)"},{"key":"1_CR28","first-page":"142","volume-title":"FOCS","author":"M.X. Goemans","year":"2005","unstructured":"Goemans, M.X., Mirrokni, V.S., Vetta, A.: Sink equilibria and convergence. In: FOCS, pp. 142\u2013154. IEEE Computer Society, Los Alamitos (2005)"},{"issue":"2","key":"1_CR29","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R.L. Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics\u00a017(2), 416\u2013429 (1969)","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"3","key":"1_CR30","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1145\/331499.331504","volume":"31","author":"A.K. Jain","year":"1999","unstructured":"Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: A review. ACM Comput. Surv.\u00a031(3), 264\u2013323 (1999)","journal-title":"ACM Comput. Surv."},{"key":"1_CR31","first-page":"215","volume-title":"Local Search in Combinatorial Optimization","author":"D.S. Johnson","year":"1997","unstructured":"Johnson, D.S., McGeoch, L.A.: The Traveling Salesman Problem: A Case Study. In: Aarts, E.H.L., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 215\u2013310. Wiley and Sons, New York (1997)"},{"issue":"1","key":"1_CR32","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimtriou, C.H., Yannakakis, M.: How easy is local search? Journal of Computer and System Science\u00a037(1), 79\u2013100 (1988)","journal-title":"Journal of Computer and System Science"},{"issue":"2","key":"1_CR33","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1090\/S0273-0979-1992-00285-9","volume":"26","author":"G. Kalai","year":"1992","unstructured":"Kalai, G., Kleitman, D.J.: A quasi-polynomial bound for the diameter of graphs of polyhedra. American Mathematical Socity\u00a026(2), 315\u2013316 (1992)","journal-title":"American Mathematical Socity"},{"issue":"4","key":"1_CR34","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica\u00a04(4), 373\u2013396 (1984)","journal-title":"Combinatorica"},{"key":"1_CR35","unstructured":"Khachiyan, L.G.: A polynomial algorithm in linear programming. In: Doklady Akademia Nauk SSSR, pp. 1093\u20131096 (1979)"},{"key":"1_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/3-540-61422-2_123","volume-title":"Algorithm Theory - SWAT \u201996","author":"H. Klauck","year":"1996","unstructured":"Klauck, H.: On the hardness of global and local approximation. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 88\u201399. Springer, Heidelberg (1996)"},{"key":"1_CR37","unstructured":"Kochetov, Y., Ivanenko, D.: Computationally difficult instances for the uncapacitated facility location problem. In: Proceedings MIC 2003 (2003)"},{"key":"1_CR38","first-page":"216","volume-title":"FOCS","author":"M.W. Krentel","year":"1989","unstructured":"Krentel, M.W.: Structure in locally optimal solutions (extended abstract). In: FOCS, pp. 216\u2013221. IEEE, Los Alamitos (1989)"},{"issue":"4","key":"1_CR39","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1137\/0219052","volume":"19","author":"M.W. Krentel","year":"1990","unstructured":"Krentel, M.W.: On finding and verifying locally optimal solutions. SIAM Journal on Computing\u00a019(4), 742\u2013749 (1990)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"1_CR40","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"C.E. Lemke Jr.","year":"1964","unstructured":"Lemke Jr., C.E., Howsen, J.T.: Equilibrium points of bimatrix games. SIAM Journal on Applied Mathematics\u00a012(2), 413\u2013423 (1964)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"1_CR41","doi-asserted-by":"crossref","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","volume":"44","author":"S. Lin","year":"1965","unstructured":"Lin, S.: Computer solutions of the traveling salesman problem. Bell System Technical Journal\u00a044, 2245\u20132269 (1965)","journal-title":"Bell System Technical Journal"},{"issue":"2","key":"1_CR42","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S. Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Operations Research\u00a021(2), 498\u2013516 (1973)","journal-title":"Operations Research"},{"key":"1_CR43","volume-title":"manuscript","author":"G.S. Lueker","year":"1975","unstructured":"Lueker, G.S.: Manuscript. Princeton University, Princeton (1975)"},{"key":"1_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/978-3-540-74456-6_56","volume-title":"Mathematical Foundations of Computer Science 2007","author":"M. Mavronicolas","year":"2007","unstructured":"Mavronicolas, M., Milchtaich, I., Monien, B., Tiemann, K.: Congestion games with player-specific constants. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 633\u2013644. Springer, Heidelberg (2007)"},{"issue":"1","key":"1_CR45","doi-asserted-by":"publisher","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 and Economic Behavior\u00a013(1), 111\u2013124 (1996)","journal-title":"Games and Economic Behavior"},{"key":"1_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/11944874_9","volume-title":"Internet and Network Economics","author":"I. Milchtaich","year":"2006","unstructured":"Milchtaich, I.: The equilibrium existence problem in finite network congestion games. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol.\u00a04286, pp. 87\u201398. Springer, Heidelberg (2006)"},{"key":"1_CR47","doi-asserted-by":"crossref","unstructured":"Monien, B., Tscheuschner, T.: On the power of nodes of degree four in the local max-cut problem. In: Diaz, J. (ed.) Proceedings of the 7th International Conference on Algorithms and Complexity, Rome, Italy (2010)","DOI":"10.1007\/978-3-642-13073-1_24"},{"key":"1_CR48","first-page":"587","volume-title":"Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms (SODA)","author":"J.B. Orlin","year":"2004","unstructured":"Orlin, J.B., Punnen, A.P., Schulz, A.S.: Approximate local search in combinatorial optimization. In: Ian Munro, J. (ed.) Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), pp. 587\u2013596. SIAM, Philadelphia (2004)"},{"key":"1_CR49","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1145\/100216.100274","volume-title":"STOC 1990: Proceedings of the twenty-second annual ACM symposium on Theory of computing","author":"C.H. Papadimitriou","year":"1990","unstructured":"Papadimitriou, C.H., Sch\u00e4ffer, A.A., Yannakakis, M.: On the complexity of local search. In: STOC 1990: Proceedings of the twenty-second annual ACM symposium on Theory of computing, pp. 438\u2013445. ACM Press, New York (1990)"},{"issue":"3","key":"1_CR50","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/0221030","volume":"21","author":"C.H. Papadimitriou","year":"1992","unstructured":"Papadimitriou, C.H.: The complexity of the lin-kernighan heuristic for the traveling salesman problem. SIAM J. Comput.\u00a021(3), 450\u2013465 (1992)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1_CR51","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci.\u00a048(3), 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1_CR52","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1137\/S0097539793245350","volume":"24","author":"S. Poljak","year":"1995","unstructured":"Poljak, S.: Integer linear programs and local search for max-cut. SIAM J. Comput.\u00a024(4), 822\u2013839 (1995)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1_CR53","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/j.orl.2004.05.011","volume":"33","author":"O.A. Prokopyev","year":"2005","unstructured":"Prokopyev, O.A., Huang, H.-X., Pardalos, P.M.: On complexity of unconstrained hyperbolic 0-1 programming problems. Operations Research Letters\u00a033(3), 312\u2013318 (2005)","journal-title":"Operations Research Letters"},{"key":"1_CR54","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1111\/j.1468-0262.2006.00667.x","volume":"74","author":"B. Stengel von","year":"2006","unstructured":"von Stengel, B., Savani, R.: Hard-to-solve bimatrix games. Econometrica\u00a074, 397\u2013429 (2006)","journal-title":"Econometrica"},{"issue":"4","key":"1_CR55","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G. Reinelt","year":"1991","unstructured":"Reinelt, G.: Tsplib - a traveling salesman problem library. INFORMS Journal on Computing\u00a03(4), 376\u2013384 (1991)","journal-title":"INFORMS Journal on Computing"},{"key":"1_CR56","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"R.W. Rosenthal","year":"1973","unstructured":"Rosenthal, R.W.: A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory\u00a02, 65\u201367 (1973)","journal-title":"International Journal of Game Theory"},{"issue":"1","key":"1_CR57","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/0220004","volume":"20","author":"A.A. Sch\u00e4ffer","year":"1991","unstructured":"Sch\u00e4ffer, A.A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM J. Comput.\u00a020(1), 56\u201387 (1991)","journal-title":"SIAM J. Comput."},{"key":"1_CR58","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BFb0121248","volume":"1","author":"L.S. Shapley","year":"2009","unstructured":"Shapley, L.S.: A note on the lemke-howson algorithm. Pivoting and Extension\u00a01, 175\u2013189 (2009)","journal-title":"Pivoting and Extension"},{"issue":"1-2","key":"1_CR59","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/S0304-3975(96)00135-1","volume":"172","author":"S. Shimozono","year":"1997","unstructured":"Shimozono, S.: Finding optimal subgraphs by local search. Theoretical Computer Science\u00a0172(1-2), 265\u2013271 (1997)","journal-title":"Theoretical Computer Science"},{"key":"1_CR60","first-page":"355","volume-title":"STOC","author":"A. Skopalik","year":"2008","unstructured":"Skopalik, A., V\u00f6cking, B.: Inapproximability of pure nash equilibria. In: Ladner, R.E., Dwork, C. (eds.) STOC, pp. 355\u2013364. ACM, New York (2008)"},{"key":"1_CR61","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02591902","volume":"27","author":"S. Smale","year":"1983","unstructured":"Smale, S.: On the average number of steps in the simplex method of linear programming. Mathematical Programming\u00a027, 241\u2013262 (1983)","journal-title":"Mathematical Programming"},{"key":"1_CR62","unstructured":"Roberto, S.-O.: Local search. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall\/Crc Computer & Information Science Series, Chapman & Hall\/CRC (2007)"},{"issue":"3","key":"1_CR63","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D.A. Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM\u00a051(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"issue":"3","key":"1_CR64","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s101070100261","volume":"91","author":"M.J. Todd","year":"2001","unstructured":"Todd, M.J.: The many facets of linear programming. Mathematical Programming\u00a091(3), 417\u2013436 (2001)","journal-title":"Mathematical Programming"},{"issue":"4","key":"1_CR65","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1287\/moor.12.4.718","volume":"12","author":"P. Kleinschmidt","year":"1987","unstructured":"Kleinschmidt, P., Klee, V.: The d-step conjecture and its relatives. Mathematics of Operations Research\u00a012(4), 718\u2013755 (1987)","journal-title":"Mathematics of Operations Research"},{"key":"1_CR66","doi-asserted-by":"crossref","unstructured":"Vattani, A.: k-means requires exponentially many iterations even in the plane. In: Hershberger, J., Fogel, E. (eds.) Proceedings of the 25th ACM Symposium on Computational Geometry, Aarhus, Denmark, pp. 324\u2013332 (2009)","DOI":"10.1145\/1542362.1542419"},{"key":"1_CR67","first-page":"159","volume-title":"Inequalities III","author":"G.J. Minty","year":"1972","unstructured":"Minty, G.J., Klee, V.: How good is the simplex algorithm? In: Inequalities III, pp. 159\u2013175. Academic Press, New York (1972)"},{"key":"1_CR68","doi-asserted-by":"crossref","unstructured":"von Stengel, B.: Computing equilibria for two-person games. In: Handbook of game theory, vol.\u00a03, pp. 1726\u20131759 (2002)","DOI":"10.1016\/S1574-0005(02)03008-4"},{"issue":"1","key":"1_CR69","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/S0167-6377(02)00165-7","volume":"31","author":"T. Vredeveld","year":"2003","unstructured":"Vredeveld, T., Lenstra, J.K.: On local search for the generalized graph coloring problem. Operations Research Letters\u00a031(1), 28\u201334 (2003)","journal-title":"Operations Research Letters"},{"key":"1_CR70","first-page":"19","volume-title":"Local Search in Combinatorial Optimization","author":"M. Yannakakis","year":"1997","unstructured":"Yannakakis, M.: Computational complexity. In: Aarts, E.H.L., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 19\u201355. Wiley, Chichester (1997)"},{"key":"1_CR71","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/3-540-52282-4_52","volume-title":"STACS 90","author":"M. Yannakakis","year":"1990","unstructured":"Yannakakis, M.: The analysis of local search problems and their heuristics. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol.\u00a0415, pp. 298\u2013311. Springer, Heidelberg (1990)"},{"issue":"2","key":"1_CR72","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.cosrev.2009.03.004","volume":"3","author":"M. Yannakakis","year":"2009","unstructured":"Yannakakis, M.: Equilibria, fixed points, and complexity classes. Computer Science Review\u00a03(2), 71\u201385 (2009)","journal-title":"Computer Science Review"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T16:31:37Z","timestamp":1740241897000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":72,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}