{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:20:54Z","timestamp":1725603654755},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_65","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"772-783","source":"Crossref","is-referenced-by-count":1,"title":["Smoothed Performance Guarantees for Local Search"],"prefix":"10.1007","author":[{"given":"Tobias","family":"Brunsch","sequence":"first","affiliation":[]},{"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[]},{"given":"Cyriel","family":"Rutten","sequence":"additional","affiliation":[]},{"given":"Tjark","family":"Vredeveld","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"65_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/11671541_2","volume-title":"Efficient Approximation and Online Algorithms","author":"E. Angel","year":"2006","unstructured":"Angel, E.: A survey of approximation results for local search algorithms. In: Bampis, E., Jansen, K., Kenyon, C. (eds.) Efficient Approximation and Online Algorithms. LNCS, vol.\u00a03484, pp. 30\u201373. Springer, Heidelberg (2006)"},{"issue":"3","key":"65_CR2","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J. Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S.A., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM\u00a044(3), 486\u2013504 (1997)","journal-title":"Journal of the ACM"},{"key":"65_CR3","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0361, 200\u2013209 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"65_CR4","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1287\/moor.1050.0170","volume":"31","author":"L. Becchetti","year":"2006","unstructured":"Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Sch\u00e4fer, G., Vredeveld, T.: Average case and smoothed competitive analysis for the multi-level feedback algorithm. Mathematics of Operations Research\u00a031(3), 85\u2013108 (2006)","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"65_CR5","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/j.jcss.2004.04.004","volume":"69","author":"R. Beier","year":"2004","unstructured":"Beier, R., V\u00f6cking, B.: Random knapsack in expected polynomial time. Journal of Computer and System Sciences\u00a069(3), 306\u2013329 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"65_CR6","doi-asserted-by":"crossref","unstructured":"Brunsch, T., R\u00f6glin, H., Rutten, C., Vredeveld, T.: Smoothed Performance Guarantees for Local Search. ArXiv e-prints (May 2011), http:\/\/arxiv.org\/abs\/1105.2686","DOI":"10.1007\/978-3-642-23719-5_65"},{"key":"65_CR7","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y. Cho","year":"1980","unstructured":"Cho, Y., Sahni, S.: Bounds for list schedules on uniform processors. SIAM Journal on Computing\u00a09, 91\u2013103 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"65_CR8","doi-asserted-by":"crossref","unstructured":"Czumaj, A., V\u00f6cking, B.: Tight bounds for worst-case equilibria. Transactions on Algorithms ACM\u00a03(1) (2007)","DOI":"10.1145\/1219944.1219949"},{"key":"65_CR9","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1295\u20131304 (2007)"},{"key":"65_CR10","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01930985","volume":"19","author":"G. Finn","year":"1979","unstructured":"Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT\u00a019, 312\u2013320 (1979)","journal-title":"BIT"},{"key":"65_CR11","volume-title":"Computers and Intractibility: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractibility: A Guide to the Theory of NP-Completeness. W.H.\u00a0Freeman & Co., New York (1979)"},{"key":"65_CR12","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics\u00a05, 287\u2013326 (1979)","journal-title":"Annals of Discrete Mathematics"},{"key":"65_CR13","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"D.S. Hochbaum","year":"1988","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for machine scheduling on uniform processors: using the dual approximation approach. SIAM Journal on Computing\u00a017, 539\u2013551 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"65_CR14","doi-asserted-by":"crossref","unstructured":"Hoefer, M., Souza, A.: Tradeoffs and average-case equilibria in selfish routing. ACM Transactions on Computation Theory 2(1), article 2 (2010)","DOI":"10.1145\/1867719.1867721"},{"key":"65_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.ijpe.2008.09.003","volume":"116","author":"J.Y.T. Leung","year":"2008","unstructured":"Leung, J.Y.T., Li, C.L.: Scheduling with processing set restrictions: A survey. International Journal of Production Economics\u00a0116, 251\u2013262 (2008)","journal-title":"International Journal of Production Economics"},{"key":"65_CR16","volume-title":"Theoretical Aspects of Local Search","author":"W.P.A.J. Michiels","year":"2007","unstructured":"Michiels, W.P.A.J., Aarts, E.H.L., Korst, J.H.M.: Theoretical Aspects of Local Search. Springer, Heidelberg (2007)"},{"key":"65_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-642-12200-2_11","volume-title":"LATIN 2010: Theoretical Informatics","author":"D. Recalde","year":"2010","unstructured":"Recalde, D., Rutten, C., Schuurman, P., Vredeveld, T.: Local search performance guarantees for restricted related parallel machine scheduling. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 108\u2013119. Springer, Heidelberg (2010)"},{"issue":"1-3","key":"65_CR18","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2005.04.006","volume":"341","author":"G. Sch\u00e4fer","year":"2005","unstructured":"Sch\u00e4fer, G., Sivadasan, N.: Topology matters: Smoothed competitiveness of metrical task systems. Theoretical Computer Science\u00a0341(1-3), 3\u201314 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"65_CR19","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1287\/ijoc.1050.0152","volume":"19","author":"P. Schuurman","year":"2007","unstructured":"Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. Informs Journal on Computing\u00a019(1), 52\u201363 (2007)","journal-title":"Informs Journal on Computing"},{"issue":"3","key":"65_CR20","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. Journal of the ACM\u00a051(3), 385\u2013463 (2004)","journal-title":"Journal of the ACM"},{"issue":"10","key":"65_CR21","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"D.A. Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Communications of the ACM\u00a052(10), 76\u201384 (2009)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_65","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T12:08:07Z","timestamp":1560514087000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}