{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:15Z","timestamp":1740109575016,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T00:00:00Z","timestamp":1581033600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T00:00:00Z","timestamp":1581033600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Science Foundation","award":["1363193"],"award-info":[{"award-number":["1363193"]}]},{"DOI":"10.13039\/100007185","name":"University of California, Los Angeles","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,3]]},"DOI":"10.1007\/s00454-020-00178-z","type":"journal-article","created":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T11:04:05Z","timestamp":1581073445000},"page":"405-424","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Number of Integer Points in Translated and Expanded Polyhedra"],"prefix":"10.1007","volume":"65","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1695-4242","authenticated-orcid":false,"given":"Danny","family":"Nguyen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Pak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,7]]},"reference":[{"key":"178_CR1","unstructured":"Alhajjar, E.: A new valuation on lattice polytopes. PhD thesis, George Mason University (2017)"},{"key":"178_CR2","first-page":"753","volume-title":"Recent Trends in Combinatorics. The IMA Volumes in Mathematics and Its Applications","author":"I Aliev","year":"2016","unstructured":"Aliev, I., De Loera, J.A., Louveaux, Q.: Parametric polyhedra with at least $$k$$ lattice points: their semigroup structure and the $$k$$-Frobenius problem. In: Beveridge, A., et al. (eds.) Recent Trends in Combinatorics. The IMA Volumes in Mathematics and Its Applications, vol. 159, pp. 753\u2013778. Springer, Cham (2016)"},{"issue":"2","key":"178_CR3","doi-asserted-by":"publisher","first-page":"42","DOI":"10.37236\/2887","volume":"20","author":"I Aliev","year":"2013","unstructured":"Aliev, I., Henk, M., Linke, E.: Integer points in knapsack polytopes and $$s$$-covering radius. Electron. J. Comb. 20(2), 42 (2013)","journal-title":"Electron. J. Comb."},{"key":"178_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"issue":"4","key":"178_CR5","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s10208-011-9106-4","volume":"12","author":"V Baldoni","year":"2012","unstructured":"Baldoni, V., Berline, N., De Loera, J.A., K\u00f6ppe, M., Vergne, M.: Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra. Found. Comput. Math. 12(4), 435\u2013469 (2012)","journal-title":"Found. Comput. Math."},{"key":"178_CR6","unstructured":"Barvinok, A.I.: A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS\u201993), pp. 566\u2013572. IEEE, Los Alamitos (1993)"},{"issue":"255","key":"178_CR7","doi-asserted-by":"publisher","first-page":"1449","DOI":"10.1090\/S0025-5718-06-01836-9","volume":"75","author":"A Barvinok","year":"2006","unstructured":"Barvinok, A.: Computing the Ehrhart quasi-polynomial of a rational simplex. Math. Comput. 75(255), 1449\u20131466 (2006)","journal-title":"Math. Comput."},{"key":"178_CR8","first-page":"763","volume-title":"International Congress of Mathematicians","author":"A Barvinok","year":"2006","unstructured":"Barvinok, A.: The complexity of generating functions for integer points in polyhedra and beyond. In: Sanz-Sol\u00e9, M., et al. (eds.) International Congress of Mathematicians, vol. 3, pp. 763\u2013787. EMS, Z\u00fcrich (2006)"},{"key":"178_CR9","doi-asserted-by":"publisher","DOI":"10.4171\/052","volume-title":"Integer Points in Polyhedra. Zurich Lectures in Advanced Mathematics","author":"A Barvinok","year":"2008","unstructured":"Barvinok, A.: Integer Points in Polyhedra. Zurich Lectures in Advanced Mathematics. EMS, Z\u00fcrich (2008)"},{"key":"178_CR10","first-page":"185","volume-title":"Handbook of Discrete and Computational Geometry","author":"A Barvinok","year":"2017","unstructured":"Barvinok, A.: Lattice points and lattice polytopes. In: Goodman, J.E., et al. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn, pp. 185\u2013210. CRC Press, Boca Raton (2017)","edition":"3"},{"key":"178_CR11","first-page":"91","volume-title":"New Perspectives in Algebraic Combinatorics. Mathematical Sciences Research Institute Publications","author":"A Barvinok","year":"1999","unstructured":"Barvinok, A., Pommersheim, J.E.: An algorithmic theory of lattice points in polyhedra. In: Billera, L.J., et al. (eds.) New Perspectives in Algebraic Combinatorics. Mathematical Sciences Research Institute Publications, vol. 38, pp. 91\u2013147. Cambridge University Press, Cambridge (1999)"},{"issue":"4","key":"178_CR12","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1090\/S0894-0347-03-00428-4","volume":"16","author":"A Barvinok","year":"2003","unstructured":"Barvinok, A., Woods, K.: Short rational generating functions for lattice point problems. J. Am. Math. Soc. 16(4), 957\u2013979 (2003)","journal-title":"J. Am. Math. Soc."},{"key":"178_CR13","doi-asserted-by":"crossref","unstructured":"Beck, M., Robins, S.: A formula related to the Frobenius problem in two dimensions. In: Number Theory, pp. 17\u201323. Springer, New York (2004)","DOI":"10.1007\/978-1-4419-9060-0_2"},{"issue":"3","key":"178_CR14","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/j.jcta.2007.05.009","volume":"115","author":"M Beck","year":"2008","unstructured":"Beck, M., Sam, S.V., Woods, K.M.: Maximal periods of (Ehrhart) quasi-polynomials. J. Comb. Theory A 115(3), 517\u2013525 (2008)","journal-title":"J. Comb. Theory A"},{"key":"178_CR15","doi-asserted-by":"publisher","first-page":"27","DOI":"10.37236\/1924","volume":"12","author":"D Beihoffer","year":"2005","unstructured":"Beihoffer, D., Hendry, J., Nijenhuis, A., Wagon, S.: Faster algorithms for Frobenius numbers. Electron. J. Comb. 12, 27 (2005)","journal-title":"Electron. J. Comb."},{"key":"178_CR16","first-page":"687","volume-title":"Recent Trends in Combinatorics. The IMA Volumes in Mathematics and its Applications","author":"B Braun","year":"2016","unstructured":"Braun, B.: Unimodality problems in Ehrhart theory. In: Beveridge, A., et al. (eds.) Recent Trends in Combinatorics. The IMA Volumes in Mathematics and its Applications, vol. 159, pp. 687\u2013711. Springer, Cham (2016)"},{"issue":"1","key":"178_CR17","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1287\/moor.1050.0169","volume":"31","author":"JA De Loera","year":"2006","unstructured":"De Loera, J.A., Hemmecke, R., K\u00f6ppe, M., Weismantel, R.: Integer polynomial optimization in fixed dimension. Math. Oper. Res. 31(1), 147\u2013153 (2006)","journal-title":"Math. Oper. Res."},{"key":"178_CR18","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., H\u00e4hnle, N.: Minimizing the number of lattice points in a translated polygon. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912), pp. 1123\u20131130. SIAM, Philadelphia (2012)","DOI":"10.1137\/1.9781611973105.80"},{"issue":"4","key":"178_CR19","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1287\/moor.1080.0320","volume":"33","author":"F Eisenbrand","year":"2008","unstructured":"Eisenbrand, F., Shmonin, G.: Parametric integer programming in fixed dimension. Math. Oper. Res. 33(4), 839\u2013850 (2008)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"178_CR20","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/j.ejc.2010.11.001","volume":"32","author":"L Fukshansky","year":"2011","unstructured":"Fukshansky, L., Sch\u00fcrmann, A.: Bounds on generalized Frobenius numbers. Eur. J. Comb. 32(3), 361\u2013368 (2011)","journal-title":"Eur. J. Comb."},{"key":"178_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. W.H. Freeman, San Francisco (1979)"},{"key":"178_CR22","first-page":"39","volume-title":"Polyhedral Combinatorics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"R Kannan","year":"1990","unstructured":"Kannan, R.: Test sets for integer programs, $$\\forall \\exists $$ sentences. In: Cook, W., Seymour, P.D. (eds.) Polyhedral Combinatorics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 1, pp. 39\u201347. American Mathematical Society, Providence, RI (1990)"},{"issue":"2","key":"178_CR23","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF01204720","volume":"12","author":"R Kannan","year":"1992","unstructured":"Kannan, R.: Lattice translates of a polytope and the Frobenius problem. Combinatorica 12(2), 161\u2013177 (1992)","journal-title":"Combinatorica"},{"key":"178_CR24","unstructured":"Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)"},{"issue":"2","key":"178_CR25","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/0022-0000(78)90044-2","volume":"16","author":"KL Manders","year":"1978","unstructured":"Manders, K.L., Adleman, L.: NP-complete decision problems for binary quadratics. J. Comput. Syst. Sci. 16(2), 168\u2013184 (1978)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"178_CR26","doi-asserted-by":"publisher","first-page":"164","DOI":"10.37236\/6059","volume":"25","author":"TB McAllister","year":"2018","unstructured":"McAllister, T.B., Rochais, H.O.: Periods of Ehrhart coefficients of rational polytopes. Electron. J. Comb. 25(1), 164 (2018)","journal-title":"Electron. J. Comb."},{"key":"178_CR27","unstructured":"Nguyen, D., Pak, I.: The computational complexity of integer programming with alternations. Math. Oper. Res. (to appear). Extended abstract in Proceedings of the 32nd Computational Complexity Conference, Art. No. 6, pp.\u00a06:1\u20136:18 (2017)"},{"key":"178_CR28","doi-asserted-by":"crossref","unstructured":"Nguyen, D., Pak, I.: Short Presburger arithmetic is hard. SIAM J. Comp. (to appear). Extended abstract in Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, pp. 37\u201348 (2017)","DOI":"10.1109\/FOCS.2017.13"},{"key":"178_CR29","doi-asserted-by":"publisher","first-page":"e1","DOI":"10.1017\/fms.2017.29","volume":"6","author":"D Nguyen","year":"2018","unstructured":"Nguyen, D., Pak, I.: Complexity of short generating functions. Forum Math. Sigma 6, e1 (2018)","journal-title":"Forum Math. Sigma"},{"key":"178_CR30","unstructured":"Pak, I.: Lectures on discrete and polyhedral geometry. Monograph draft. http:\/\/www.math.ucla.edu\/~pak\/book.htm (2009)"},{"key":"178_CR31","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"issue":"1","key":"178_CR32","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF01300131","volume":"16","author":"JL Ram\u00edrez Alfons\u00edn","year":"1996","unstructured":"Ram\u00edrez Alfons\u00edn, J.L.: Complexity of the Frobenius problem. Combinatorica 16(1), 143\u2013147 (1996)","journal-title":"Combinatorica"},{"key":"178_CR33","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198568209.001.0001","volume-title":"The Diophantine Frobenius Problem. Oxford Lecture Series in Mathematics and its Applications","author":"JL Ram\u00edrez Alfons\u00edn","year":"2005","unstructured":"Ram\u00edrez Alfons\u00edn, J.L.: The Diophantine Frobenius Problem. Oxford Lecture Series in Mathematics and its Applications, vol. 30. Oxford University Press, Oxford (2005)"},{"key":"178_CR34","volume-title":"Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. Wiley, Chichester (1986)"},{"issue":"2","key":"178_CR35","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.jsc.2007.07.007","volume":"43","author":"S Verdoolaege","year":"2008","unstructured":"Verdoolaege, S., Woods, K.: Counting with rational generating functions. J. Symb. Comput. 43(2), 75\u201391 (2008)","journal-title":"J. Symb. Comput."},{"key":"178_CR36","unstructured":"Woods, K.: Rational generating functions and lattice point sets. PhD thesis, University of Michigan (2004)"},{"key":"178_CR37","doi-asserted-by":"publisher","first-page":"34","DOI":"10.37236\/1931","volume":"12","author":"K Woods","year":"2005","unstructured":"Woods, K.: Computing the period of an Ehrhart quasi-polynomial. Electron. J. Comb. 12, 34 (2005)","journal-title":"Electron. J. Comb."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00178-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-020-00178-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00178-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T19:59:04Z","timestamp":1612900744000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-020-00178-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,7]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["178"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00178-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2020,2,7]]},"assertion":[{"value":"1 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 December 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}