{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T06:28:36Z","timestamp":1775716116144,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T00:00:00Z","timestamp":1687737600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T00:00:00Z","timestamp":1687737600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Rheinland-Pf\u00e4lzische Technische Universit\u00e4t Kaiserslautern-Landau"}],"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>We study the approximation of general multiobjective optimization problems with the help of scalarizations. Existing results state that multiobjective minimization problems can be approximated well by norm-based scalarizations. However, for multiobjective maximization problems, only impossibility results are known so far. Countering this, we show that all multiobjective optimization problems can, in principle, be approximated equally well by scalarizations. In this context, we introduce a transformation theory for scalarizations that establishes the following: Suppose there exists a scalarization that yields an approximation of a certain quality for arbitrary instances of multiobjective optimization problems with a given decomposition specifying which objective functions are to be minimized\/maximized. Then, for each other decomposition, our transformation yields another scalarization that yields the same approximation quality for arbitrary instances of problems with this other decomposition. In this sense, the existing results about the approximation via scalarizations for minimization problems carry over to any other objective decomposition\u2014in particular, to maximization problems\u2014when suitably adapting the employed scalarization. We further provide necessary and sufficient conditions on a scalarization such that its optimal solutions achieve a constant approximation quality. We give an upper bound on the best achievable approximation quality that applies to general scalarizations and is tight for the majority of norm-based scalarizations applied in the context of multiobjective optimization. As a consequence, none of these norm-based scalarizations can induce approximation sets for optimization problems with maximization objectives, which unifies and generalizes the existing impossibility results concerning the approximation of maximization problems.<\/jats:p>","DOI":"10.1007\/s00186-023-00823-2","type":"journal-article","created":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T21:01:54Z","timestamp":1687813314000},"page":"27-63","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Using scalarizations for the approximation of multiobjective optimization problems: towards a general theory"],"prefix":"10.1007","volume":"100","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6588-5266","authenticated-orcid":false,"given":"Stephan","family":"Helfrich","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"}]},{"given":"Clemens","family":"Thielen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,6,26]]},"reference":[{"key":"823_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.jda.2013.06.006","volume":"22","author":"C Bazgan","year":"2013","unstructured":"Bazgan C, Gourv\u00e8s L, Monnot J (2013) Approximation with a fixed number of solutions of some multiobjective maximization problems. J Discrete Algorithms 22:19\u201329","journal-title":"J Discrete Algorithms"},{"issue":"1","key":"823_CR2","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"},{"key":"823_CR3","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s00224-021-10066-5","volume":"66","author":"C Bazgan","year":"2022","unstructured":"Bazgan C, Ruzika S, Thielen C, Vanderpooten D (2022) The power of the weighted sum scalarization for approximating multiobjective optimization problems. Theory Comput Syst 66:395\u2013415","journal-title":"Theory Comput Syst"},{"key":"823_CR4","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-662-48350-3_25","volume-title":"Algorithms\u2014ESA 2015","author":"F B\u00f6kler","year":"2015","unstructured":"B\u00f6kler F, Mutzel P (2015) Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. In: Bansal N, Finocchi I (eds) Algorithms\u2014ESA 2015. Springer, Berlin Heidelberg, pp 288\u2013299"},{"issue":"3","key":"823_CR5","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1137\/13093875X","volume":"45","author":"C Daskalakis","year":"2016","unstructured":"Daskalakis C, Diakonikolas I, Yannakakis M (2016) How good is the chord algorithm? SIAM J Comput 45(3):811\u2013858","journal-title":"SIAM J Comput"},{"key":"823_CR6","unstructured":"Diakonikolas I, Yannakakis M (2008) Succinct approximate convex Pareto curves. In: Teng SH (ed) Proceedings of the 19th annual ACM-SIAM symposium on discrete algorithms (SODA). SIAM, pp 74\u201383"},{"issue":"4","key":"823_CR7","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":"823_CR8","volume-title":"Multicriteria optimization","author":"M Ehrgott","year":"2005","unstructured":"Ehrgott M (2005) Multicriteria optimization. Springer"},{"issue":"4","key":"823_CR9","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s002910000046","volume":"22","author":"M Ehrgott","year":"2000","unstructured":"Ehrgott M, Gandibleux X (2000) A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectr 22(4):425\u2013460","journal-title":"OR Spectr"},{"key":"823_CR10","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1007\/0-387-23081-5_17","volume-title":"Multiple criteria decision analysis: state of the art surveys","author":"M Ehrgott","year":"2005","unstructured":"Ehrgott M, Wiecek M (2005) Multiobjective programming. In: Figueira J, Greco S, Ehrgott M (eds) Multiple criteria decision analysis: state of the art surveys. Springer, New York, pp 667\u2013722"},{"issue":"173","key":"823_CR11","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1080\/01621459.1931.10503148","volume":"26","author":"WF Ferger","year":"1931","unstructured":"Ferger WF (1931) The nature and use of the harmonic mean. J Am Stat Assoc 26(173):36\u201340","journal-title":"J Am Stat Assoc"},{"key":"823_CR12","doi-asserted-by":"crossref","unstructured":"Gla\u00dfer C, Reitwie\u00dfner C, Schmitz H, Witek M (2010) Approximability and hardness in multi-objective optimization. In: Ferreira F, L\u00f6we B, Mayordomo E, Gomes LM (ed) Proceedings of the 6th conference on computability in Europe (CiE) volume 6158 of LNCS. Springer, pp 180\u2013189","DOI":"10.1007\/978-3-642-13962-8_20"},{"key":"823_CR13","doi-asserted-by":"crossref","unstructured":"Gla\u00dfer C, Reitwie\u00dfner C, Schmitz H, Witek M (2010) Hardness and approximability in multi-objective optimization. Technical report TR10-031 electronic colloquium on computational complexity (ECCC)","DOI":"10.1007\/978-3-642-13962-8_20"},{"issue":"1\u20132","key":"823_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.07.003","volume":"695","author":"P Halffmann","year":"2017","unstructured":"Halffmann P, Ruzika S, Thielen C, Willems D (2017) A general approximation method for bicriteria minimization problems. Theor Comput Sci 695(1\u20132):1\u201315","journal-title":"Theor Comput Sci"},{"key":"823_CR15","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s10898-023-01276-x","volume":"86","author":"A Herzel","year":"2023","unstructured":"Herzel A, Helfrich S, Ruzika S, Thielen C (2023) Approximating biobjective minimization problems using general ordering cones. J Global Optim 86:393\u2013415","journal-title":"J Global Optim"},{"key":"823_CR16","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10898-020-00951-7","volume":"80","author":"A Herzel","year":"2021","unstructured":"Herzel A, Bazgan C, Ruzika S, Thielen C, Vanderpooten D (2021) One-exact approximate Pareto sets. J Global Optim 80:87\u2013115","journal-title":"J Global Optim"},{"issue":"4","key":"823_CR17","first-page":"1284","volume":"33","author":"A Herzel","year":"2021","unstructured":"Herzel A, Ruzika S, Thielen C (2021) Approximation methods for multiobjective optimization problems: A survey. INFORMS J Comput 33(4):1284\u20131299","journal-title":"INFORMS J Comput"},{"issue":"2","key":"823_CR18","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1016\/j.ejor.2018.05.036","volume":"271","author":"T Holzmann","year":"2018","unstructured":"Holzmann T, Smith J (2018) Solving discrete multi-objective optimization problems using modified augmented weighted Tchebychev scalarizations. Eur J Oper Res 271(2):436\u2013449","journal-title":"Eur J Oper Res"},{"key":"823_CR19","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-7091-2822-0_3","volume-title":"Mathematics of multi objective optimization","author":"J Jahn","year":"1985","unstructured":"Jahn J (1985) Scalarization in multi objective optimization. In: Serafini P (ed) Mathematics of multi objective optimization. Springer, Vienna, pp 45\u201388"},{"issue":"3","key":"823_CR20","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1016\/j.ejor.2015.03.031","volume":"245","author":"K Klamroth","year":"2015","unstructured":"Klamroth K, Lacour R, Vanderpooten D (2015) On the representation of the search region in multi-objective optimization. Eur J Oper Res 245(3):767\u2013778","journal-title":"Eur J Oper Res"},{"issue":"3","key":"823_CR21","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":"2","key":"823_CR22","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00291-001-0092-9","volume":"24","author":"K Miettinen","year":"2002","unstructured":"Miettinen K, M\u00e4kel\u00e4 M (2002) On scalarizing functions in multiobjective optimization. OR Spectr 24(2):193\u2013213","journal-title":"OR Spectr"},{"key":"823_CR23","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). IEEE, pp 86\u201392","DOI":"10.1109\/SFCS.2000.892068"},{"key":"823_CR24","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-642-46618-2_15","volume-title":"Recent advances and historical development of vector optimization, volume 294 of lecture notes in economics and mathematical systems","author":"P Serafini","year":"1987","unstructured":"Serafini P (1987) Some considerations about computational complexity for multi objective combinatorial problems. In: Jahn J, Krabs W (eds) Recent advances and historical development of vector optimization, volume 294 of lecture notes in economics and mathematical systems. Springer, pp 222\u2013232"},{"issue":"3","key":"823_CR25","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/s10898-016-0426-4","volume":"67","author":"D Vanderpooten","year":"2016","unstructured":"Vanderpooten D, Weerasena L, Wiecek MM (2016) Covers and approximations in multiobjective optimization. J Global Optim 67(3):601\u2013619","journal-title":"J Global Optim"},{"issue":"2\u20133","key":"823_CR26","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"},{"issue":"2","key":"823_CR27","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01719738","volume":"8","author":"AP Wierzbicki","year":"1986","unstructured":"Wierzbicki AP (1986) On the completeness and constructiveness of parametric characterizations to vector optimization problems. Oper Res Spektrum 8(2):73\u201387","journal-title":"Oper Res Spektrum"},{"key":"823_CR28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00823-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-023-00823-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00823-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T09:04:58Z","timestamp":1725267898000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-023-00823-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,26]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["823"],"URL":"https:\/\/doi.org\/10.1007\/s00186-023-00823-2","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"value":"1432-2994","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,26]]},"assertion":[{"value":"29 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 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":"Conflict of interest"}}]}}