{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T17:13:45Z","timestamp":1710522825986},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,3,1]],"date-time":"2017-03-01T00:00:00Z","timestamp":1488326400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s11786-017-0297-1","type":"journal-article","created":{"date-parts":[[2017,3,24]],"date-time":"2017-03-24T02:01:32Z","timestamp":1490320892000},"page":"35-48","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximating Multidimensional Subset Sum and Minkowski Decomposition of Polygons"],"prefix":"10.1007","volume":"11","author":[{"given":"Ioannis Z.","family":"Emiris","sequence":"first","affiliation":[]},{"given":"Anna","family":"Karasoulou","sequence":"additional","affiliation":[]},{"given":"Charilaos","family":"Tzovas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,3,24]]},"reference":[{"key":"297_CR1","doi-asserted-by":"crossref","unstructured":"Abu-Salem, F., Gao, S., Lauder, A.G.B.: Factoring polynomials via polytopes. In: Proceedings of ACM Internernational Symposium on Symbolic and Algebraic Computation, po. 4\u201311 (2004)","DOI":"10.1145\/1005285.1005289"},{"key":"297_CR2","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S Arora","year":"1997","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54, 317\u2013331 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"297_CR3","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximations. In: Proceedings of ACM STOC, pp. 294\u2013304. ACM (1993)","DOI":"10.1145\/167088.167174"},{"key":"297_CR4","doi-asserted-by":"crossref","unstructured":"Bringmann, K.: A near-linear pseudopolynomial time algorithm for subset sum. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, USA, pp. 1073\u20131084. SIAM (2017)","DOI":"10.1137\/1.9781611974782.69"},{"key":"297_CR5","volume-title":"Real Analysis. Cambridge Books Online","author":"NL Carothers","year":"2000","unstructured":"Carothers, N.L.: Real Analysis. Cambridge Books Online. Cambridge University Press, Cambridge (2000)"},{"key":"297_CR6","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, London (2009)","edition":"3"},{"issue":"2","key":"297_CR7","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s00493-003-0019-y","volume":"23","author":"I Dinur","year":"2003","unstructured":"Dinur, I., Kindler, G., Raz, R., Safra, S.: Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica 23(2), 205\u2013243 (2003)","journal-title":"Combinatorica"},{"key":"297_CR8","unstructured":"Emiris, I.Z., Karasoulou, A., Tzanaki, E., Zafeirakopoulos, Z.: On the space of Minkowski summands of a convex polytope. In: 32st European Workshop on Computational Geometry (EuroCG), Book of Abstracts, pp. 35\u201338 (2016)"},{"key":"297_CR9","unstructured":"Emiris, I.Z., Karasoulou, A., Tzovas, C.: Approximating multidimensional subset sum and the Minkowski decomposition of polygons. In: European Workshop on Computational Geometry (EuroCG), Book of Abstracts, pp. 119\u2013122 (2016)"},{"key":"297_CR10","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/978-3-540-33275-6_14","volume-title":"Algebraic Geometry and Geometric Modeling, Mathematics and Visualization","author":"IZ Emiris","year":"2006","unstructured":"Emiris, I.Z., Tsigaridas, E.: Minkowski decomposition of convex lattice polygons. In: Elkadi, M., Mourrain, B., Piene, R. (eds.) Algebraic Geometry and Geometric Modeling, Mathematics and Visualization, pp. 217\u2013236. Springer, Berlin (2006)"},{"issue":"2","key":"297_CR11","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1006\/jabr.2000.8586","volume":"237","author":"S Gao","year":"2001","unstructured":"Gao, S.: Absolute irreducibility of polynomials via newton polytopes. J. Algebra 237(2), 501\u2013520 (2001)","journal-title":"J. Algebra"},{"issue":"1","key":"297_CR12","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/s00454-001-0024-0","volume":"26","author":"S Gao","year":"2001","unstructured":"Gao, S., Lauder, A.G.B.: Decomposition of polytopes and polynomials. Discrete Comput. Geom. 26(1), 89\u2013104 (2001)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"297_CR13","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s10107-002-0315-0","volume":"94","author":"M Henk","year":"2003","unstructured":"Henk, M., K\u00f6ppe, M., Weismantel, R.: Integral decomposition of polyhedra and some applications in mixed integer programming. Math. Program. 94(2), 193\u2013206 (2003)","journal-title":"Math. Program."},{"issue":"4","key":"297_CR14","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463\u2013468 (1975)","journal-title":"J. ACM"},{"issue":"5","key":"297_CR15","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/j.jsc.2007.11.005","volume":"43","author":"E Kaltofen","year":"2008","unstructured":"Kaltofen, E., May, J.P., Yang, Z., Zhi, L.: Approximate factorization of multivariate polynomials using singular value decomposition. J. Symb. Comput. 43(5), 359\u2013376 (2008)","journal-title":"J. Symb. Comput."},{"key":"297_CR16","unstructured":"Kesh, D., Mehta, S.: Polynomial irreducibility testing through Minkowski summand computation. In: Proceedings of Canadian Conference on Computational Geometry, pp. 43\u201346 (2008)"},{"key":"297_CR17","unstructured":"Koiliaris, K., Xu, C.: A faster pseudopolynomial time algorithm for subset sum. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA \u201917, pp. 1062\u20131072, Philadelphia, USA, (2017). SIAM. Also available as: arXiv:1507.02318"},{"issue":"16","key":"297_CR18","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1016\/j.ipl.2010.05.031","volume":"110","author":"A Kulik","year":"2010","unstructured":"Kulik, A., Shachnai, H.: There is no EPTAS for two-dimensional knapsack. Inf. Process. Lett. 110(16), 707\u2013710 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"297_CR19","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1287\/moor.9.2.244","volume":"9","author":"MJ Magazine","year":"1984","unstructured":"Magazine, M.J., Chern, M.-S.: A note on approximation schemes for multidimensional knapsack problems. Math. Oper. Res. 9(2), 244\u2013247 (1984)","journal-title":"Math. Oper. Res."},{"key":"297_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01836201","volume":"14","author":"AM Ostrowski","year":"1976","unstructured":"Ostrowski, A.M.: On multiplication and factorization of polynomials. II. Irreducibility discussion. Aequ. Math. 14, 1\u201331 (1976)","journal-title":"Aequ. Math."},{"key":"297_CR21","unstructured":"Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of an FPTAS? In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA \u201999, Philadelphia, USA, pp. 820\u2013829. SIAM (1999)"},{"issue":"1","key":"297_CR22","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1287\/ijoc.12.1.57.11901","volume":"12","author":"GJ Woeginger","year":"2000","unstructured":"Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS J. Comput. 12(1), 57\u201374 (2000)","journal-title":"INFORMS J. Comput."}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-017-0297-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11786-017-0297-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-017-0297-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,25]],"date-time":"2017-06-25T09:21:13Z","timestamp":1498382473000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11786-017-0297-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["297"],"URL":"https:\/\/doi.org\/10.1007\/s11786-017-0297-1","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"value":"1661-8270","type":"print"},{"value":"1661-8289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3]]}}}