{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T14:57:29Z","timestamp":1768402649152,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,2,7]],"date-time":"2019-02-07T00:00:00Z","timestamp":1549497600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s10898-019-00745-6","type":"journal-article","created":{"date-parts":[[2019,2,7]],"date-time":"2019-02-07T02:24:01Z","timestamp":1549506241000},"page":"495-522","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions"],"prefix":"10.1007","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8528-3331","authenticated-orcid":false,"given":"Britta","family":"Schulze","sequence":"first","affiliation":[]},{"given":"Kathrin","family":"Klamroth","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Stiglmayr","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,2,7]]},"reference":[{"issue":"1","key":"745_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-015-0944-8","volume":"154","author":"H Aissi","year":"2015","unstructured":"Aissi, H., Mahjoub, A.R., McCormick, S.T., Queyranne, M.: Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs. Math. Program. 154(1), 3\u201328 (2015)","journal-title":"Math. Program."},{"issue":"1","key":"745_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1287\/mnsc.25.1.73","volume":"25","author":"YP Aneja","year":"1979","unstructured":"Aneja, Y.P., Nair, K.P.K.: Bicriteria transportation problem. Manag. Sci. 25(1), 73\u201378 (1979)","journal-title":"Manag. Sci."},{"issue":"1","key":"745_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1023\/A:1004605810296","volume":"105","author":"HP Benson","year":"2000","unstructured":"Benson, H.P., Sun, E.: Outcome space partition of the weight set in multiobjective linear programming. J. Optim. Theory Appl. 105(1), 17\u201336 (2000)","journal-title":"J. Optim. Theory Appl."},{"key":"745_CR4","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/S0377-2217(01)00153-9","volume":"139","author":"HP Benson","year":"2002","unstructured":"Benson, H.P., Sun, E.: A weight set decomposition algorithm for finding all efficient extreme points in the outcome set of a multiple objective linear program. Eur. J. Oper. Res. 139, 26\u201341 (2002)","journal-title":"Eur. J. Oper. Res."},{"issue":"9","key":"745_CR5","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"C\u201328","author":"JL Bentley","year":"1979","unstructured":"Bentley, J.L., Ottmann, T.A.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. C\u201328(9), 643\u2013647 (1979)","journal-title":"IEEE Trans. Comput."},{"key":"745_CR6","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-662-48350-3_25","volume-title":"Algorithms\u2013ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14\u201316, 2015, Proceedings","author":"F B\u00f6kler","year":"2015","unstructured":"B\u00f6kler, F., Mutzel, P.: Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. In: Bansal, N., Finocchi, I. (eds.) Algorithms\u2013ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14\u201316, 2015, Proceedings, pp. 288\u2013299. Springer, Berlin (2015)"},{"issue":"1\u20132","key":"745_CR7","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1002\/mcda.1603","volume":"24","author":"F B\u00f6kler","year":"2017","unstructured":"B\u00f6kler, F., Ehrgott, M., Morris, C., Mutzel, P.: Output-sensitive complexity of multiobjective combinatorial optimization. J. Multicrit. Decis. Anal. 24(1\u20132), 25\u201336 (2017)","journal-title":"J. Multicrit. Decis. Anal."},{"issue":"9","key":"745_CR8","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1080\/00029890.1943.11991447","volume":"50","author":"R Buck","year":"1943","unstructured":"Buck, R.: Partition of space. Am. Math. Mon. 50(9), 541\u2013544 (1943)","journal-title":"Am. Math. Mon."},{"key":"745_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer, Berlin (1987)"},{"key":"745_CR10","volume-title":"Multicriteria Optimization","author":"M Ehrgott","year":"2005","unstructured":"Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2005)"},{"key":"745_CR11","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s002910000046","volume":"22","author":"M Ehrgott","year":"2000","unstructured":"Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum 22, 425\u2013460 (2000)","journal-title":"OR Spektrum"},{"key":"745_CR12","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/s10898-011-9709-y","volume":"52","author":"M Ehrgott","year":"2012","unstructured":"Ehrgott, M., L\u00f6hne, A., Shao, L.: A dual variant of Benson\u2019s \u201couter approximation algorithm\u201d for multiple objective linear programming. J. Global Optim. 52, 757\u2013778 (2012)","journal-title":"J. Global Optim."},{"key":"745_CR13","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.ejor.2003.04.011","volume":"166","author":"JA Ferrez","year":"2005","unstructured":"Ferrez, J.A., Fukuda, K., Liebling, T.M.: Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm. Eur. J. Oper. Res. 166, 35\u201350 (2005)","journal-title":"Eur. J. Oper. Res."},{"key":"745_CR14","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1002\/mcda.1574","volume":"24","author":"JR Figueira","year":"2017","unstructured":"Figueira, J.R., Fonseca, C.M., Halffmann, P., Klamroth, K., Paquete, L., Ruzika, S., Schulze, B., Stiglmayr, M., Willems, D.: Easy to say they are hard, but hard to see they are easy: towards a categorization of tractable multiobjective combinatorial optimization problems. J. Multi-Crit. Decis. Anal. 24, 82\u201398 (2017)","journal-title":"J. Multi-Crit. Decis. Anal."},{"key":"745_CR15","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1002\/nav.3800020106","volume":"2","author":"S Gaas","year":"1955","unstructured":"Gaas, S., Saaty, T.: The computational algorithm for the parametric objective function. Naval Res. Logist. Q. 2, 39\u201345 (1955)","journal-title":"Naval Res. Logist. Q."},{"key":"745_CR16","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1016\/0022-247X(68)90201-1","volume":"22","author":"AM Geoffrion","year":"1968","unstructured":"Geoffrion, A.M.: Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl. 22, 618\u2013630 (1968)","journal-title":"J. Math. Anal. Appl."},{"issue":"2","key":"745_CR17","doi-asserted-by":"publisher","first-page":"836","DOI":"10.1137\/060674831","volume":"19","author":"F Heyde","year":"2008","unstructured":"Heyde, F., L\u00f6hne, A.: Geometric duality in multiple objective linear programming. SIAM J. Optim. 19(2), 836\u2013845 (2008)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"745_CR18","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 4(4), 373\u2013395 (1984)","journal-title":"Combinatorica"},{"key":"745_CR19","unstructured":"Lacour, R., Klamroth, K., Fonseca, C.M.: A box decomposition algorithm to compute the hypervolume indicator. (2015). CoRR \n                    arXiv:1510.01963"},{"issue":"12","key":"745_CR20","doi-asserted-by":"publisher","first-page":"2302","DOI":"10.1287\/mnsc.1100.1248","volume":"56","author":"\u00d6 \u00d6zpeynirci","year":"2010","unstructured":"\u00d6zpeynirci, \u00d6., K\u00f6ksalan, M.: An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs. Manag. Sci. 56(12), 2302\u20132315 (2010)","journal-title":"Manag. Sci."},{"issue":"5","key":"745_CR21","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1287\/opre.45.5.758","volume":"46","author":"D Pisinger","year":"1997","unstructured":"Pisinger, D.: A minimal algorithm for the \n                    \n                      \n                    \n                    $$0$$\n                    \n                      \n                        \n                          0\n                        \n                      \n                    \n                  \u2013\n                    \n                      \n                    \n                    $$1$$\n                    \n                      \n                        \n                          1\n                        \n                      \n                    \n                   knapsack problem. Oper. Res. 46(5), 758\u2013767 (1997)","journal-title":"Oper. Res."},{"key":"745_CR22","unstructured":"Pisinger, D.: Minknap algorithm (2015). \n                    http:\/\/www.diku.dk\/~pisinger\/codes.html"},{"issue":"3","key":"745_CR23","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1287\/ijoc.1090.0342","volume":"22","author":"A Przybylski","year":"2010","unstructured":"Przybylski, A., Gandibleux, X., Ehrgott, M.: A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme. INFORMS J. Comput. 22(3), 371\u2013386 (2010)","journal-title":"INFORMS J. Comput."},{"key":"745_CR24","unstructured":"Przybylski, A., Klamroth, K., Lacour, R.: A simple and efficient dichotomic search algorithm for multi-objective integer linear programmes, submitted manuscript (2017)"},{"key":"745_CR25","unstructured":"Schulze, B.: New perspectives on multi-objective knapsack problems. Ph.D. Thesis, Shaker Verlag, Aachen (2017)"},{"key":"745_CR26","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.cor.2016.07.012","volume":"78","author":"B Schulze","year":"2017","unstructured":"Schulze, B., Paquete, L., Klamroth, K., Figueira, J.R.: Bi-dimensional knapsack problems with one soft constraint. Comput. Oper. Res. 78, 15\u201326 (2017)","journal-title":"Comput. Oper. Res."},{"key":"745_CR27","volume-title":"On Adjacency, Cardinality, and Partial Dominance in Discrete Multiple Objective Optimization","author":"F Seipp","year":"2013","unstructured":"Seipp, F.: On Adjacency, Cardinality, and Partial Dominance in Discrete Multiple Objective Optimization. Dr. Hut Verlag, M\u00fcnchen (2013)"},{"key":"745_CR28","unstructured":"Gomes\u00a0da Silva, C., Cl\u00edmaco, G., Figueira, J.R.: Geometrical configuration of the Pareto frontier of bi-criteria \n                    \n                      \n                    \n                    $$\\{0,1\\}$$\n                    \n                      \n                        \n                          {\n                          0\n                          ,\n                          1\n                          }\n                        \n                      \n                    \n                  -knapsack problems. Research Report 16-2004, INESC-Coimbra, Portugal (2004)"},{"key":"745_CR29","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1023\/A:1008258310679","volume":"12","author":"M Vis\u00e9e","year":"1998","unstructured":"Vis\u00e9e, M., Teghem, J., Pirlot, M., Ulungu, E.L.: Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem. J. Global Optim. 12, 139\u2013155 (1998)","journal-title":"J. Global Optim."},{"key":"745_CR30","volume-title":"Integer Programming. Series in Discrete Mathematics and Optimization","author":"LA Wolsey","year":"1998","unstructured":"Wolsey, L.A.: Integer Programming. Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York (1998)"},{"key":"745_CR31","first-page":"1","volume":"154","author":"T Zaslavsky","year":"1975","unstructured":"Zaslavsky, T.: Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Mem. Am. Math. Soc. 154, 1\u201395 (1975)","journal-title":"Mem. Am. Math. Soc."},{"key":"745_CR32","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/BFb0056872","volume-title":"Parallel Problem Solving from Nature\u2014PPSN V","author":"E Zitzler","year":"1998","unstructured":"Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms: a comparative case study. In: Eiben, A.E., B\u00e4ck, T., Schoenauer, M., Schwefel, H.P. (eds.) Parallel Problem Solving from Nature\u2014PPSN V, pp. 292\u2013301. Springer, Berlin (1998)"},{"issue":"2","key":"745_CR33","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TEVC.2003.810758","volume":"7","author":"E Zitzler","year":"2003","unstructured":"Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Grunert da Fonseca, V.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2), 117\u2013132 (2003)","journal-title":"IEEE Trans. Evol. Comput."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10898-019-00745-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-019-00745-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-019-00745-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,6]],"date-time":"2020-02-06T19:17:34Z","timestamp":1581016654000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10898-019-00745-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,7]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["745"],"URL":"https:\/\/doi.org\/10.1007\/s10898-019-00745-6","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,7]]},"assertion":[{"value":"30 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}