{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T02:35:45Z","timestamp":1783046145753,"version":"3.54.6"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T00:00:00Z","timestamp":1694822400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T00:00:00Z","timestamp":1694822400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004563","name":"Bayerisches Staatsministerium f\u00fcr Bildung und Kultus, Wissenschaft und Kunst","doi-asserted-by":"publisher","award":["ADA-Center"],"award-info":[{"award-number":["ADA-Center"]}],"id":[{"id":"10.13039\/501100004563","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004563","name":"Bayerisches Staatsministerium f\u00fcr Bildung und Kultus, Wissenschaft und Kunst","doi-asserted-by":"publisher","award":["ADA-Center"],"award-info":[{"award-number":["ADA-Center"]}],"id":[{"id":"10.13039\/501100004563","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the optimal piecewise linear interpolation of the bivariate product <jats:italic>xy<\/jats:italic> over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as building blocks, we construct a triangulation scheme called <jats:italic>crossing swords<\/jats:italic> that requires at most \"Equation missing\"- times the number of simplices in any optimal triangulation. In other words, we derive an approximation algorithm for the optimal triangulation problem. We also show that crossing swords yields optimal triangulations in the case that each simplex has at least one axis-parallel edge. Furthermore, we present approximation guarantees for other well-known triangulation schemes, namely for the red refinement and longest-edge bisection strategies as well as for a generalized version of K1-triangulations. Thereby, we are able to show that our novel approach dominates previous triangulation schemes from the literature, which is underlined by illustrative numerical examples.\n<\/jats:p>","DOI":"10.1007\/s10957-023-02292-3","type":"journal-article","created":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T05:02:00Z","timestamp":1694840520000},"page":"569-599","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["An Approximation Algorithm for Optimal Piecewise Linear Interpolations of Bounded Variable Products"],"prefix":"10.1007","volume":"199","author":[{"given":"Andreas","family":"B\u00e4rmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Burlacu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5002-2919","authenticated-orcid":false,"given":"Lukas","family":"Hager","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Katja","family":"Kutzer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,9,16]]},"reference":[{"issue":"2","key":"2292_CR1","doi-asserted-by":"publisher","first-page":"198","DOI":"10.3390\/math10020198","volume":"10","author":"L Alkhalifa","year":"2022","unstructured":"Alkhalifa, L., Mittelmann, H.: New algorithm to solve mixed integer quadratically constrained quadratic programming problems using piecewise linear approximation. Mathematics 10(2), 198 (2022)","journal-title":"Mathematics"},{"issue":"1","key":"2292_CR2","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s13366-017-0351-9","volume":"59","author":"D Atariah","year":"2018","unstructured":"Atariah, D., Rote, G., Wintraecken, M.: Optimal triangulation of saddle surfaces. Contribut. Algebra Geom. 59(1), 113\u2013126 (2018)","journal-title":"Contribut. Algebra Geom."},{"key":"2292_CR3","doi-asserted-by":"crossref","unstructured":"Aurenhammer, F., Xu, Y.-F.: Optimal triangulations. In: Encyclopedia of Optimization. Springer, pp. 2757\u20132764 (2008)","DOI":"10.1007\/978-0-387-74759-0_475"},{"key":"2292_CR4","first-page":"3","volume":"1","author":"RE Bank","year":"1983","unstructured":"Bank, R.E., Sherman, A.H., Weiser, A.: Some refinement algorithms and data structures for regular local mesh refinement. Sci. Comput. Appl. Math. Comput. Phys. Sci. 1, 3\u201317 (1983)","journal-title":"Sci. Comput. Appl. Math. Comput. Phys. Sci."},{"key":"2292_CR5","doi-asserted-by":"crossref","unstructured":"B\u00e4rmann, A., Burlacu, R., Hager, L., Kleinert, T.: On piecewise linear approximations of bilinear terms: structural comparison of univariate and bivariate mixed-integer programming formulations. J. Global Optim. pp. 1\u201331 (2022)","DOI":"10.1007\/s10898-022-01243-y"},{"key":"2292_CR6","unstructured":"Beach, B., Hildebrand, R., Huchette, J.: Compact mixed-integer programming relaxations in quadratic optimization. arXiv preprint arXiv:2011.08823. (2020)"},{"issue":"3","key":"2292_CR7","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s00453-002-0962-9","volume":"34","author":"O Beaumont","year":"2002","unstructured":"Beaumont, O., Boudet, V., Rastello, F., Robert, Y., et al.: Partitioning a square into rectangles: NP-completeness and approximation algorithms. Algorithmica 34(3), 217\u2013239 (2002)","journal-title":"Algorithmica"},{"issue":"16","key":"2292_CR8","first-page":"635","volume":"2","author":"R Burlacu","year":"2021","unstructured":"Burlacu, R.: On refinement strategies for solving MINLPs by piecewise linear relaxations: a generalized red refinement. Optim. Lett. 2(16), 635\u2013652 (2021)","journal-title":"Optim. Lett."},{"key":"2292_CR9","unstructured":"Burlacu, R.: Adaptive Mixed-Integer Refinements for Solving Nonlinear Problems with Discrete Decisions. PhD thesis. Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg (FAU) (2020)"},{"key":"2292_CR10","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1090\/S0025-5718-2011-02495-6","volume":"81","author":"A Cohen","year":"2012","unstructured":"Cohen, A., Dyn, N., Hecht, F., Mirebeau, J.-M.: Adaptive multiresolution analysis based on anisotropic triangulations. Math. Comput. 81, 789\u2013810 (2012)","journal-title":"Math. Comput."},{"issue":"2","key":"2292_CR11","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s11081-014-9249-7","volume":"15","author":"A F\u00fcgenschuh","year":"2014","unstructured":"F\u00fcgenschuh, A., Hayn, C., Michaels, D.: Mixed-integer linear methods for layout-optimization of screening systems in recovered paper production. Optim. Eng. 15(2), 533\u2013573 (2014)","journal-title":"Optim. Eng."},{"issue":"11","key":"2292_CR12","doi-asserted-by":"publisher","first-page":"1637","DOI":"10.1080\/02331934.2012.728217","volume":"63","author":"A F\u00fcgenschuh","year":"2014","unstructured":"F\u00fcgenschuh, A., Junosza-Szaniawski, K., Lonc, Z.: Exact and approximation algorithms for a soft rectangle packing problem. Optimization 63(11), 1637\u20131663 (2014)","journal-title":"Optimization"},{"key":"2292_CR13","unstructured":"Gei\u00dfler, B.: Towards Globally Optimal Solutions for MINLPs by Discretization Techniques with Applications in Gas Network Optimization. PhD thesis (2011)"},{"key":"2292_CR14","doi-asserted-by":"crossref","unstructured":"Gei\u00dfler, B., Martin, A., Morsi, A., Schewe, L.: Using piecewise linear functions for solving MINLPs. In: Mixed Integer Nonlinear Programming. Springer, pp. 287\u2013314 (2012)","DOI":"10.1007\/978-1-4614-1927-3_10"},{"key":"2292_CR15","unstructured":"Kutzer, K.: Using Piecewise Linear Approximation Techniques to Handle Bilinear Constraints. PhD thesis. Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg (FAU) (2020)"},{"issue":"4","key":"2292_CR16","doi-asserted-by":"publisher","first-page":"1475","DOI":"10.1137\/100793955","volume":"21","author":"C Lu","year":"2011","unstructured":"Lu, C., Fang, S.-C., Jin, Q., Wang, Z., Xing, W.: KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems. SIAM J. Optim. 21(4), 1475\u20131490 (2011)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2292_CR17","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1080\/00029890.1970.11992441","volume":"77","author":"P Monsky","year":"1970","unstructured":"Monsky, P.: On dividing a square into triangles. Am. Math. Mon. 77(2), 161\u2013164 (1970)","journal-title":"Am. Math. Mon."},{"key":"2292_CR18","doi-asserted-by":"crossref","unstructured":"Morsi, A., Gei\u00dfler, B., Martin, A.: Mixed Integer Optimization of Water Supply Networks. In: Mathematical Optimization of Water Networks. Vol. 162. Springer, pp. 35\u201354 (2012)","DOI":"10.1007\/978-3-0348-0436-3_3"},{"issue":"1","key":"2292_CR19","first-page":"31","volume":"4","author":"H Pottmann","year":"2000","unstructured":"Pottmann, H., Krasauskas, R., Hamann, B., Joy, K., Seibold, W.: On piecewise linear approximation of quadratic functions. J. Geom. Graph. 4(1), 31\u201353 (2000)","journal-title":"J. Geom. Graph."},{"issue":"1","key":"2292_CR20","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/s10957-014-0688-2","volume":"167","author":"S Rebennack","year":"2015","unstructured":"Rebennack, S., Kallrath, J.: Continuous piecewise linear deltaapproximations for bivariate and multivariate functions. J. Optim. Theory Appl. 167(1), 102\u2013117 (2015)","journal-title":"J. Optim. Theory Appl."},{"key":"2292_CR21","doi-asserted-by":"crossref","unstructured":"Todd, M.J.: Hamiltonian triangulations of Rn. In: Peitgen, H.-O., Walther, H.-O. (eds) Functional Differential Equations and Approximation of Fixed Points. Springer, Berlin, pp. 470\u2013483 (1979)","DOI":"10.1007\/BFb0064331"},{"issue":"2","key":"2292_CR22","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1287\/opre.1090.0721","volume":"58","author":"JP Vielma","year":"2010","unstructured":"Vielma, J.P., Ahmed, S., Nemhauser, G.: Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions. Oper. Res. 58(2), 303\u2013315 (2010)","journal-title":"Oper. Res."},{"key":"2292_CR23","unstructured":"Zelmer, A.: Designing Coupled Energy Carrier Networks By Mixed-Integer Programming Methods. PhD thesis. Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg (FAU) (2010)"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02292-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-023-02292-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02292-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,1]],"date-time":"2023-11-01T21:20:34Z","timestamp":1698873634000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-023-02292-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,16]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["2292"],"URL":"https:\/\/doi.org\/10.1007\/s10957-023-02292-3","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,16]]},"assertion":[{"value":"18 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 September 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}