{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T03:52:34Z","timestamp":1769313154037,"version":"3.49.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T00:00:00Z","timestamp":1605657600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T00:00:00Z","timestamp":1605657600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001655","name":"German Academic Exchange Service","doi-asserted-by":"crossref","award":["57388848"],"award-info":[{"award-number":["57388848"]}],"id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["RU 1524\/6-1"],"award-info":[{"award-number":["RU 1524\/6-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["TH 1852\/4-1"],"award-info":[{"award-number":["TH 1852\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100006537","name":"Campus France","doi-asserted-by":"crossref","award":["40407WF"],"award-info":[{"award-number":["40407WF"]}],"id":[{"id":"10.13039\/501100006537","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2021,5]]},"abstract":"Abstract<\/jats:title>Papadimitriou and Yannakakis (Proceedings of the 41st annual IEEE symposium on the Foundations of Computer Science (FOCS), pp 86\u201392, 2000) show that the polynomial-time solvability of a certain auxiliary problem determines the class of multiobjective optimization problems that admit a polynomial-time computable $$(1+\\varepsilon , \\dots , 1+\\varepsilon )$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n ,<\/mml:mo>\n \u22ef<\/mml:mo>\n ,<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximate Pareto set (also called an $$\\varepsilon $$<\/jats:tex-math>\n \u03b5<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Pareto set<\/jats:italic>). Similarly, in this article, we characterize the class of multiobjective optimization problems having a polynomial-time computable approximate $$\\varepsilon $$<\/jats:tex-math>\n \u03b5<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Pareto set that is exact in one objective<\/jats:italic> by the efficient solvability of an appropriate auxiliary problem. This class includes important problems such as multiobjective shortest path and spanning tree, and the approximation guarantee we provide is, in general, best possible. Furthermore, for biobjective optimization problems from this class, we provide an algorithm that computes a one-exact $$\\varepsilon $$<\/jats:tex-math>\n \u03b5<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Pareto set of cardinality at most twice the cardinality of a smallest such set and show that this factor of 2 is best possible. For three or more objective functions, however, we prove that no constant-factor approximation on the cardinality of the set can be obtained efficiently.<\/jats:p>","DOI":"10.1007\/s10898-020-00951-7","type":"journal-article","created":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T05:05:30Z","timestamp":1605675930000},"page":"87-115","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["One-exact approximate Pareto sets"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6230-1253","authenticated-orcid":false,"given":"Arne","family":"Herzel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristina","family":"Bazgan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Ruzika","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[[2020,11,18]]},"reference":[{"key":"951_CR1","doi-asserted-by":"crossref","unstructured":"Angel, E., Bampis, E., Kononov, A.: A FPTAS for approximating the unrelated parallel machines scheduling problem with costs. In: Proceedings of the 9th Annual European Symposium on Algorithms (ESA), LNCS, vol. 2161, pp. 194\u2013205 (2001)","DOI":"10.1007\/3-540-44676-1_16"},{"key":"951_CR2","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/S0304-3975(03)00288-3","volume":"306","author":"E Angel","year":"2003","unstructured":"Angel, E., Bampis, E., Kononov, A.: On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems. Theor. Comput. Sci. 306, 319\u2013338 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"951_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.: Approximate Pareto sets of minimal size for multi-objective optimization problems. Oper. Res. Lett. 43(1), 1\u20136 (2015)","journal-title":"Oper. Res. Lett."},{"key":"951_CR4","unstructured":"B\u00f6kler, F.: Output-sensitive complexity of multiobjective combinatorial optimization with an application to the multiobjective shortest path problem. Ph.D. thesis, Technical University of Dortmund (2018)"},{"issue":"1\u20132","key":"951_CR5","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. Multi-Criteria Decis. Anal. 24(1\u20132), 25\u201336 (2017)","journal-title":"J. Multi-Criteria Decis. Anal."},{"issue":"4","key":"951_CR6","doi-asserted-by":"publisher","first-page":"1340","DOI":"10.1137\/080724514","volume":"39","author":"I Diakonikolas","year":"2009","unstructured":"Diakonikolas, I., Yannakakis, M.: Small approximate Pareto sets for biobjective shortest paths and other problems. SIAM J. Comput. 39(4), 1340\u20131371 (2009)","journal-title":"SIAM J. Comput."},{"key":"951_CR7","doi-asserted-by":"crossref","unstructured":"Ehrgott, M.: 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 (1998)","DOI":"10.1007\/978-3-642-57311-8_5"},{"key":"951_CR8","volume-title":"Multicriteria Optimization","author":"M Ehrgott","year":"2005","unstructured":"Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2005)"},{"issue":"5","key":"951_CR9","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0020-0190(02)00205-3","volume":"83","author":"F Ergun","year":"2002","unstructured":"Ergun, F., Sinha, R., Zhang, L.: An improved FPTAS for restricted shortest path. Inf. Process. Lett. 83(5), 287\u2013291 (2002)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"951_CR10","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s10107-013-0703-7","volume":"146","author":"F Grandoni","year":"2014","unstructured":"Grandoni, F., Ravi, R., Singh, M., Zenklusen, R.: New approaches to multi-objective optimization. Math. Program. 146(1), 525\u2013554 (2014)","journal-title":"Math. Program."},{"issue":"3","key":"951_CR11","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/s11590-017-1212-z","volume":"12","author":"M Horv\u00e1th","year":"2018","unstructured":"Horv\u00e1th, M., Kis, T.: Multi-criteria approximation schemes for the resource constrained shortest path problem. Optim. Lett. 12(3), 475\u2013483 (2018)","journal-title":"Optim. Lett."},{"issue":"3","key":"951_CR12","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.: Approximately dominating representatives. Theor. Comput. Sci. 371(3), 148\u2013154 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"951_CR13","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0167-6377(01)00069-4","volume":"28","author":"DH Lorenz","year":"2001","unstructured":"Lorenz, D.H., Raz, D.: A simple efficient approximation scheme for the restricted shortest path problem. Oper. Res. Lett. 28(5), 213\u2013219 (2001)","journal-title":"Oper. Res. Lett."},{"key":"951_CR14","unstructured":"Papadimitriou, C., Yannakakis, M.: 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 (2000)"},{"issue":"1","key":"951_CR15","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/s00224-007-9096-4","volume":"45","author":"G Tsaggouris","year":"2009","unstructured":"Tsaggouris, G., Zaroliagis, C.: Multiobjective optimization: improved FPTAS for shortest paths and non-linear objectives with applications. Theory Comput. Syst. 45(1), 162\u2013186 (2009)","journal-title":"Theory Comput. Syst."},{"issue":"2\u20133","key":"951_CR16","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.: Efficiently computing succinct trade-off curves. Theor. Comput. Sci. 348(2\u20133), 334\u2013356 (2005)","journal-title":"Theor. Comput. Sci."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-020-00951-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-020-00951-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-020-00951-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,18]],"date-time":"2021-05-18T06:14:19Z","timestamp":1621318459000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-020-00951-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,18]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["951"],"URL":"https:\/\/doi.org\/10.1007\/s10898-020-00951-7","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,18]]},"assertion":[{"value":"7 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}