{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,27]],"date-time":"2025-12-27T07:33:07Z","timestamp":1766820787392,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,9,27]],"date-time":"2023-09-27T00:00:00Z","timestamp":1695772800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,27]],"date-time":"2023-09-27T00:00:00Z","timestamp":1695772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>It is well known that, under very weak assumptions, multiobjective optimization problems admit <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1+\\varepsilon ,\\dots ,1+\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u22ef<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation sets (also called <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b5<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula><jats:italic>-Pareto sets<\/jats:italic>) of polynomial cardinality (in the size of the instance and in\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\frac{1}{\\varepsilon }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mfrac>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mi>\u03b5<\/mml:mi>\n                  <\/mml:mfrac>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>). While an approximation guarantee of <jats:inline-formula><jats:alternatives><jats:tex-math>$$1+\\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon &gt;0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the best one can expect for singleobjective problems (apart from solving the problem to optimality), even better approximation guarantees than <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1+\\varepsilon ,\\dots ,1+\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u22ef<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be considered in the multiobjective case since the approximation might be exact in some of the objectives. Hence, in this paper, we consider <jats:italic>partially exact approximation sets<\/jats:italic> that require to approximate each feasible solution exactly, i.e., with an approximation guarantee of\u00a01, in some of the objectives while still obtaining a guarantee of <jats:inline-formula><jats:alternatives><jats:tex-math>$$1+\\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in all others. We characterize the types of polynomial-cardinality, partially exact approximation sets that are guaranteed to exist for general multiobjective optimization problems. Moreover, we study minimum-cardinality partially exact approximation sets concerning (weak) efficiency of the contained solutions and relate their cardinalities to the minimum cardinality of a <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1+\\varepsilon ,\\dots ,1+\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u22ef<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation set.<\/jats:p>","DOI":"10.1007\/s00186-023-00836-x","type":"journal-article","created":{"date-parts":[[2023,9,27]],"date-time":"2023-09-27T18:02:28Z","timestamp":1695837748000},"page":"5-25","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximating multiobjective optimization problems: How exact can you be?"],"prefix":"10.1007","volume":"100","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arne","family":"Herzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Ruzika","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0897-3571","authenticated-orcid":false,"given":"Clemens","family":"Thielen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Vanderpooten","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,27]]},"reference":[{"issue":"1\u20132","key":"836_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 AR, McCormick ST, Queyranne M (2015) Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs. Math Program 154(1\u20132):3\u201328","journal-title":"Math Program"},{"issue":"3","key":"836_CR2","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/j.jctb.2005.09.003","volume":"96","author":"N Alon","year":"2006","unstructured":"Alon N, Brightwell GR, Kierstead HA, Kostochka AV, Winkler P (2006) Dominating sets in k-majority tournaments. J Comb Theory Ser B 96(3):374\u2013387","journal-title":"J Comb Theory Ser B"},{"issue":"1","key":"836_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.orl.2014.10.003","volume":"43","author":"C Bazgan","year":"2015","unstructured":"Bazgan C, Jamain F, Vanderpooten D (2015) Approximate Pareto sets of minimal size for multi-objective optimization problems. Oper Res Lett 43(1):1\u20136","journal-title":"Oper Res Lett"},{"issue":"3","key":"836_CR4","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1016\/j.ejor.2016.11.020","volume":"260","author":"C Bazgan","year":"2017","unstructured":"Bazgan C, Jamain F, Vanderpooten D (2017) Discrete representation of the non-dominated set for multi-objective optimization problems using kernels. Eur J Oper Res 260(3):814\u2013827","journal-title":"Eur J Oper Res"},{"issue":"4","key":"836_CR5","doi-asserted-by":"publisher","first-page":"1340","DOI":"10.1137\/080724514","volume":"39","author":"I Diakonikolas","year":"2009","unstructured":"Diakonikolas I, Yannakakis M (2009) Small approximate Pareto sets for biobjective shortest paths and other problems. SIAM J Comput 39(4):1340\u20131371","journal-title":"SIAM J Comput"},{"key":"836_CR6","doi-asserted-by":"crossref","unstructured":"Ehrgott M (1998) Hard to say it\u2019s easy\u2014four reasons why combinatorial multiobjective programmes are hard. In: Proceedings of the 14th international conference on multiple criteria decision making (MCDM). Lecture notes in economics and mathematical systems, vol 487, pp 69\u201380","DOI":"10.1007\/978-3-642-57311-8_5"},{"key":"836_CR7","doi-asserted-by":"crossref","unstructured":"Herzel A, Ruzika S, Thielen C (2021a) Approximation methods for multiobjective optimization problems: a survey. INFORMS J Comput 33(4):1284\u20131299","DOI":"10.1287\/ijoc.2020.1028"},{"key":"836_CR8","doi-asserted-by":"crossref","unstructured":"Herzel A, Bazgan C, Ruzika S, Thielen C, Vanderpooten D (2021b) One-exact approximate pareto sets. J Glob Optim 80(1):87\u2013115","DOI":"10.1007\/s10898-020-00951-7"},{"issue":"3","key":"836_CR9","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9(3):256\u2013278","journal-title":"J Comput Syst Sci"},{"issue":"3","key":"836_CR10","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.tcs.2006.11.003","volume":"371","author":"V Koltun","year":"2007","unstructured":"Koltun V, Papadimitriou C (2007) Approximately dominating representatives. Theor Comput Sci 371(3):148\u2013154","journal-title":"Theor Comput Sci"},{"issue":"3","key":"836_CR11","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C Papadimitriou","year":"1991","unstructured":"Papadimitriou C, Yannakakis M (1991) Optimization, approximation, and complexity classes. J Comput Syst Sci 43(3):425\u2013440","journal-title":"J Comput Syst Sci"},{"key":"836_CR12","doi-asserted-by":"crossref","unstructured":"Papadimitriou C, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. In: Proceedings of the 41st annual IEEE symposium on the foundations of computer science (FOCS), pp 86\u201392","DOI":"10.1109\/SFCS.2000.892068"},{"key":"836_CR13","unstructured":"Safer HM (1992) Fast approximation schemes for multi-criteria combinatorial optimization. PhD thesis, Massachusetts Institute of Technology"},{"key":"836_CR14","unstructured":"Safer HM, Orlin JB (1995) Fast approximation schemes for multi-criteria combinatorial optimization. Working paper 3756-95, Sloan School of Management, Massachusetts Institute of Technology"},{"issue":"2\u20133","key":"836_CR15","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1016\/j.tcs.2005.09.022","volume":"348","author":"S Vassilvitskii","year":"2005","unstructured":"Vassilvitskii S, Yannakakis M (2005) Efficiently computing succinct trade-off curves. Theor Comput Sci 348(2\u20133):334\u2013356","journal-title":"Theor Comput Sci"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00836-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-023-00836-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00836-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T09:04:06Z","timestamp":1725267846000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-023-00836-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,27]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["836"],"URL":"https:\/\/doi.org\/10.1007\/s00186-023-00836-x","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"type":"print","value":"1432-2994"},{"type":"electronic","value":"1432-5217"}],"subject":[],"published":{"date-parts":[[2023,9,27]]},"assertion":[{"value":"28 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}},{"value":"All authors contributed to the study conception and design and the writing of the manuscript. All authors read and approved the final manuscript.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Author Contributions"}}]}}