{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T05:02:39Z","timestamp":1684472559010},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T00:00:00Z","timestamp":1664236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T00:00:00Z","timestamp":1664236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"DFG grant","award":["VO 889\/2"],"award-info":[{"award-number":["VO 889\/2"]}]},{"name":"ERC Starting Grant","award":["306465"],"award-info":[{"award-number":["306465"]}]},{"name":"EU within the 6th Framework Programme","award":["001907 (DELIS)"],"award-info":[{"award-number":["001907 (DELIS)"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A well-established heuristic approach for solving bicriteria optimization problems is to enumerate the set of Pareto-optimal solutions. The heuristics following this principle are often successful in practice. Their running time, however, depends on the number of enumerated solutions, which is exponential in the worst case. We study bicriteria integer optimization problems in the model of smoothed analysis, in which inputs are subject to a small amount of random noise, and we prove an almost tight polynomial bound on the expected number of Pareto-optimal solutions. Our results give rise to tight polynomial bounds for the expected running time of the Nemhauser-Ullmann algorithm for the knapsack problem and they improve known results on the running times of heuristics for the bounded knapsack problem and the bicriteria shortest path problem.\n<\/jats:p>","DOI":"10.1007\/s10107-022-01885-6","type":"journal-article","created":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T12:10:03Z","timestamp":1664280603000},"page":"319-355","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The smoothed number of Pareto-optimal solutions in bicriteria integer optimization"],"prefix":"10.1007","volume":"200","author":[{"given":"Ren\u00e9","family":"Beier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clemens","family":"R\u00f6sner","sequence":"additional","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":[[2022,9,27]]},"reference":[{"key":"1885_CR1","unstructured":"Beier, R. : Probabilistic analysis of discrete optimization problems. PhD thesis, Universit\u00e4t des Saarlandes (2004)"},{"key":"1885_CR2","doi-asserted-by":"publisher","first-page":"237","DOI":"10.4086\/toc.2014.v010a010","volume":"10","author":"Tobias Brunsch","year":"2014","unstructured":"Brunsch, Tobias, Goyal, Navin, Rademacher, Luis, R\u00f6glin, Heiko: Lower bounds for the average and smoothed number of pareto-optima. Theor. Comput. 10, 237\u2013256 (2014)","journal-title":"Theor. Comput."},{"issue":"1","key":"1885_CR3","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/2699445","volume":"62","author":"Tobias Brunsch","year":"2015","unstructured":"Brunsch, Tobias, R\u00f6glin, Heiko: Improved smoothed analysis of multiobjective optimization. J. ACM 62(1), 4:1-4:58 (2015)","journal-title":"J. ACM"},{"key":"1885_CR4","doi-asserted-by":"crossref","unstructured":"Beier, Ren\u00e9, R\u00f6glin, Heiko, V\u00f6cking, Berthold: the smoothed number of pareto optimal solutions in bicriteria integer optimization. In: Proceedings of the 12th international conference on integer programming and combinatorial optimization (IPCO), pp. 53\u201367 (2007)","DOI":"10.1007\/978-3-540-72792-7_5"},{"issue":"3","key":"1885_CR5","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/j.jcss.2004.04.004","volume":"69","author":"Ren\u00e9 Beier","year":"2004","unstructured":"Beier, Ren\u00e9, V\u00f6cking, Berthold: Random knapsack in expected polynomial time. J. Comput. Syst. Sci. 69(3), 306\u2013329 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1885_CR6","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF00938761","volume":"46","author":"H William Corley","year":"1985","unstructured":"Corley, H William, Moon, IDouglas: Shortest paths in networks with vector weights. J. Optimiz. Theor. Appl. 46(1), 79\u201386 (1985)","journal-title":"J. Optimiz. Theor. Appl."},{"key":"1885_CR7","doi-asserted-by":"crossref","unstructured":"Diakonikolas, Ilias, Yannakakis, Mihalis: Small approximate pareto sets for bi-objective shortest paths and other problems. In: Proceedings of the 10th international workshop on approximation algorithms for combinatorial optimization problems (APPROX), pp. 74\u201388 (2007)","DOI":"10.1007\/978-3-540-74208-1_6"},{"key":"1885_CR8","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/b101915","volume-title":"Multiple criteria optimization-state of the art annotated bibliographic surveys","author":"Matthias Ehrgott","year":"2002","unstructured":"Ehrgott, Matthias: Gandibleux, Xavier: Multiobjective combinatorial optimization. In: Ehrgott, Matthias, Gandibleux, Xavier (eds.) Multiple criteria optimization-state of the art annotated bibliographic surveys, pp. 369\u2013444. Kluwer Academic Publishers (2002)"},{"key":"1885_CR9","first-page":"229","volume":"19","author":"Matthias Ehrgott","year":"1999","unstructured":"Ehrgott, Matthias: Integer solutions of multicriteria network flow problems. Investig. Oper. 19, 229\u2013243 (1999)","journal-title":"Investig. Oper."},{"key":"1885_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"Hans Kellerer","year":"2004","unstructured":"Kellerer, Hans, Pferschy, Ulrich, Pisinger, David: Knapsack Problems. Springer (2004)"},{"issue":"1","key":"1885_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1002\/(SICI)1520-6750(200002)47:1<57::AID-NAV4>3.0.CO;2-4","volume":"47","author":"Kathrin Klamroth","year":"2000","unstructured":"Klamroth, Kathrin, Wiecek, Margaret M.: Dynamic programming approaches to the multiple criteria knapsack problem. Naval Res. Logist. 47(1), 57\u201376 (2000)","journal-title":"Naval Res. Logist."},{"issue":"2","key":"1885_CR12","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0305-0548(97)00027-0","volume":"25","author":"Adli Mustafa","year":"1998","unstructured":"Mustafa, Adli, Goh, Mark: Finding integer efficient solutions for bicriteria and tricriteria network flow problems using dinas. Comput. Oper. Res. 25(2), 139\u2013157 (1998)","journal-title":"Comput. Oper. Res."},{"key":"1885_CR13","doi-asserted-by":"crossref","unstructured":"M\u00fcller-Hannemann, Matthias, Weihe, Karsten: Pareto shortest paths is often feasible in practice. In: Proceedings of the 5th international workshop on algorithm engineering (WAE), pages 185\u2013198 (2001)","DOI":"10.1007\/3-540-44688-5_15"},{"issue":"5","key":"1885_CR14","doi-asserted-by":"publisher","first-page":"1266","DOI":"10.1137\/110851833","volume":"41","author":"Ankur Moitra","year":"2012","unstructured":"Moitra, Ankur, O\u2019Donnell, Ryan: Pareto optimal solutions for smoothed analysts. SIAM J. Comput. 41(5), 1266\u20131284 (2012)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1885_CR15","first-page":"280","volume":"53","author":"Bodo Manthey","year":"2011","unstructured":"Manthey, Bodo, R\u00f6glin, Heiko: Smoothed analysis: analysis of algorithms beyond worst case. Inf. Technol. 53(6), 280\u2013286 (2011)","journal-title":"Inf. Technol."},{"key":"1885_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing","author":"Michael Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, Michael, Upfal, Eli: Probability and Computing. Cambridge University Press (2005)"},{"issue":"9","key":"1885_CR17","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1287\/mnsc.15.9.494","volume":"15","author":"George L Nemhauser","year":"1969","unstructured":"Nemhauser, George L., Ullmann, Zev: Discrete dynamic programming and capital allocation. Manag. Sci. 15(9), 494\u2013505 (1969)","journal-title":"Manag. Sci."},{"key":"1885_CR18","unstructured":"Papadimitriou, Christos\u00a0H., Yannakakis, Mihalis: On the approximability of trade-offs and optimal access of web sources. In: Proceedings of the 41st Annual IEEE symposium on foundations of computer science (FOCS), pp. 86\u201392 (2000)"},{"key":"1885_CR19","series-title":"volume 10185 of Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1007\/978-3-319-55911-7_39","volume-title":"Theory and applications of models of computation","author":"Heiko R\u00f6glin","year":"2017","unstructured":"R\u00f6glin, Heiko: R\u00f6sner, Clemens: the smoothed number of Pareto-optimal solutions in non-integer bicriteria optimization. In: Theory and applications of models of computation. volume 10185 of Lecture Notes in Computer Science, pp. 543\u2013555. Springer, Cham (2017)"},{"key":"1885_CR20","doi-asserted-by":"crossref","unstructured":"R\u00f6glin, Heiko, Teng, Shang-Hua: Smoothed analysis of multiobjective optimization. In: Proceedings of the 50th Annual IEEE symposium on foundations of computer science (FOCS), pp. 681\u2013690 (2009)","DOI":"10.1109\/FOCS.2009.21"},{"issue":"6","key":"1885_CR21","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1016\/S0305-0548(99)00037-4","volume":"27","author":"Anders JV Skriver","year":"2000","unstructured":"Skriver, Anders JV., Andersen, Kim Allan: A label correcting approach for solving bicriterion shortest-path problems. Comput. Oper. Res. 27(6), 507\u2013524 (2000)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"1885_CR22","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"Daniel A Spielman","year":"2004","unstructured":"Spielman, Daniel A., Teng, Shang-Hua.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"issue":"10","key":"1885_CR23","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"Daniel A Spielman","year":"2009","unstructured":"Spielman, Daniel A., Teng, Shang-Hua.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76\u201384 (2009)","journal-title":"Commun. ACM"},{"issue":"2","key":"1885_CR24","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1016\/j.tcs.2005.09.022","volume":"348","author":"Sergei Vassilvitskii","year":"2005","unstructured":"Vassilvitskii, Sergei, Yannakakis, Mihalis: Efficiently computing succinct trade-off curves. Theor. Comput. Sci. 348(2), 334\u2013356 (2005)","journal-title":"Theor. Comput. Sci."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01885-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01885-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01885-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T23:08:25Z","timestamp":1684451305000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01885-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,27]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1885"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01885-6","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,27]]},"assertion":[{"value":"22 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}