{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T14:00:10Z","timestamp":1758636010038},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,1,5]],"date-time":"2007-01-05T00:00:00Z","timestamp":1167955200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2007,3,12]]},"DOI":"10.1007\/s10107-006-0055-7","type":"journal-article","created":{"date-parts":[[2007,1,4]],"date-time":"2007-01-04T17:51:41Z","timestamp":1167933101000},"page":"21-56","source":"Crossref","is-referenced-by-count":17,"title":["Smoothed analysis of integer programming"],"prefix":"10.1007","volume":"110","author":[{"given":"Heiko","family":"R\u00f6glin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,1,5]]},"reference":[{"key":"55_CR1","doi-asserted-by":"crossref","unstructured":"Ackermann, H., Newman, A., R\u00f6glin, H., V\u00f6cking, B.: Decision making based on approximate and smoothed pareto curves. In: Proceedings of the 16th annual international symposium on algorithms and computation (ISAAC), pp. 675\u2013684 (2005)","DOI":"10.1007\/11602613_68"},{"key":"55_CR2","doi-asserted-by":"crossref","unstructured":"Banderier, C., Beier, R., Mehlhorn, K.: Smoothed analysis of three combinatorial problems. In: Proceedings 28th international symposium on mathematical foundations of computer science (MFCS), vol. 97, pp. 198\u2013207 (2003)","DOI":"10.1007\/978-3-540-45138-9_14"},{"key":"55_CR3","unstructured":"Beier, R., V\u00f6cking, B.: Probabilistic analysis of knapsack core algorithms. In: Proceedings of the 15th annual symposium on discrete algorithms (SODA), pp. 468\u2013477 (2004)"},{"issue":"3","key":"55_CR4","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/j.jcss.2004.04.004","volume":"69","author":"R. Beier","year":"2004","unstructured":"Beier R. and V\u00f6cking B. (2004). Random knapsack in expected polynomial time. J. Comput. Syst. Sci. 69(3): 306\u2013329","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"55_CR5","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s00453-005-1193-7","volume":"45","author":"R. Beier","year":"2006","unstructured":"Beier R. and V\u00f6cking B. (2006). An experimental study of random knapsack problems. Algorithmica 45(1): 121\u2013136","journal-title":"Algorithmica"},{"issue":"4","key":"55_CR6","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1137\/S0097539705447268","volume":"35","author":"R. Beier","year":"2006","unstructured":"Beier R. and V\u00f6cking B. (2006). Typical properties of winners and losers in discrete optimization. SIAM J. Comput. 35(4): 855\u2013881","journal-title":"SIAM J. Comput."},{"key":"55_CR7","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/jcom.1994.1005","volume":"10","author":"K.H. Borgwardt","year":"1994","unstructured":"Borgwardt K.H. and Brzank J. (1994). Average saving effects in enumerative methods for solving knapsack problems. J. Complexity 10: 129\u2013141","journal-title":"J. Complexity"},{"key":"55_CR8","unstructured":"Crescenzi, P., Kann, V., Halldorsson, M., Karpinski, M., Woeginger, G.: A compendium of np optimization problems. Http:\/\/www.nada.kth.se\/~viggo\/problemlist\/compendium.html"},{"issue":"1","key":"55_CR9","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1287\/moor.14.1.162","volume":"14","author":"M.E. Dyer","year":"1989","unstructured":"Dyer M.E. and Frieze A.M. (1989). Probabilistic analysis of the multidimensional knapsack problem. Math. Oper. Res. 14(1): 162\u2013176","journal-title":"Math. Oper. Res."},{"key":"55_CR10","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"Garey M. and Johnson D. (1979). Computers and Intractability. Freeman, W. H. Sanfroncisco"},{"key":"55_CR11","doi-asserted-by":"crossref","unstructured":"Goldberg, A., Marchetti-Spaccamela, A.: On finding the exact solution to a zero-one knapsack problem. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pp. 359\u2013368 (1984)","DOI":"10.1145\/800057.808701"},{"issue":"2","key":"55_CR12","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1006\/jagm.1998.0954","volume":"29","author":"G.S. Lueker","year":"1998","unstructured":"Lueker G.S. (1998). Average-case analysis of off-line and on-line knapsack problems. J. Algorithms 29(2): 277\u2013305","journal-title":"J. Algorithms"},{"key":"55_CR13","doi-asserted-by":"crossref","unstructured":"Manthey, B., Reischuk, R.: Smoothed analysis of binary search trees. In: Proceedings of the 16th annual international symposium on algorithms and computation (ISAAC), pp. 483\u2013492 (2005)","DOI":"10.1007\/11602613_49"},{"issue":"3","key":"55_CR14","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D.A. Spielman","year":"2004","unstructured":"Spielman D.A. and Teng S.H. (2004). Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3): 385\u2013463","journal-title":"J. ACM"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0055-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-006-0055-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0055-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T05:50:01Z","timestamp":1559109001000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-006-0055-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,5]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,3,12]]}},"alternative-id":["55"],"URL":"https:\/\/doi.org\/10.1007\/s10107-006-0055-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1,5]]}}}