{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:04:32Z","timestamp":1787321072331,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SFB\/TRR 191"],"award-info":[{"award-number":["SFB\/TRR 191"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["414898050"],"award-info":[{"award-number":["414898050"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["764759"],"award-info":[{"award-number":["764759"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>In this note we give a polynomial time algorithm for solving the closest vector problem in the class of zonotopal lattices. The Voronoi cell of a zonotopal lattice is a zonotope, i.e., a projection of a regular cube. Examples of zonotopal lattices include lattices of Voronoi's first kind and tensor products of root lattices of type $\\mathsf{A}$. The combinatorial structure of zonotopal lattices can be described by regular matroids\/totally unimodular matrices. We observe that a linear algebra version of the minimum mean cycle canceling method can be applied for efficiently solving the closest vector problem in a zonotopal lattice if the lattice is given as the integral kernel of a totally unimodular matrix.<\/jats:p>","DOI":"10.1137\/20m1382258","type":"journal-article","created":{"date-parts":[[2021,10,6]],"date-time":"2021-10-06T14:59:19Z","timestamp":1633532359000},"page":"2345-2356","source":"Crossref","is-referenced-by-count":3,"title":["A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices"],"prefix":"10.1137","volume":"35","author":[{"given":"S. Thomas","family":"McCormick","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Britta","family":"Peis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Scheidweiler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3205-4607","authenticated-orcid":true,"given":"Frank","family":"Vallentin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,10,6]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"D. Aggarwal, D. Dadush, and N. Stephens-Davidowitz,\n                      Solving the closest vector problem in $2^n$ time: The discrete Gaussian strikes again!\n                      , in Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science-FOCS 2015, IEEE, Washington, DC, 2015, pp. 563-582.","DOI":"10.1109\/FOCS.2015.41"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"atypb3","first-page":"1206","author":"Artmann S.","year":"2017","journal-title":"New York"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.2303"},{"key":"atypb5","unstructured":"A. Bj\u00f6rner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler,\n                      Oriented Matroids\n                      , Cambridge University Press, Cambridge, UK, 1993."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.01.028"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"J. H. Conway and N. J. A. Sloane,\n                      Sphere Packings, Lattices and Groups\n                      , Springer, New York, 1988.","DOI":"10.1007\/978-1-4757-2016-7"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1992.0004"},{"key":"atypb9","unstructured":"J. H. Conway,\n                      The Sensual (Quadratic) Form\n                      , with the assistance of Francis Y. C. Fung, Carus Math. Monogr. 26, Mathematical Association of America, Washington, DC, 1997."},{"key":"atypb10","first-page":"137","volume":"41","author":"H. S.","year":"1962","journal-title":"J. Math. Pure Appl."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0019-y"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-017-0332-x"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-09-02224-8"},{"key":"atypb14","unstructured":"P. van Emde Boas,\n                      Another NP-complete Problem and the Complexity of Computing Short Vectors in a Lattice\n                      , Tech. rep. 81-04, Department of Mathematics, University of Amsterdam, The Netherlands, 1981."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1994.1049"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1999.0294"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456412"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76368"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/96559.96597"},{"key":"atypb20","first-page":"261","author":"Hunkenschr\u00f6der C.","year":"2019","journal-title":"Berlin"},{"key":"atypb21","first-page":"257","volume":"16","author":"Jaeger F.","year":"1983","journal-title":"Ars Combin. B"},{"key":"atypb22","first-page":"78","author":"Karzanov A. V.","year":"1995","journal-title":"Philadelphia"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794263695"},{"key":"atypb24","unstructured":"H.F. Loesch,\n                      Zur Reduktionstheorie von Delone-Voronoi f\u00fcr matroidische quadratische Formen\n                      , Dissertation, Ruhr-Universit\u00e4t Bochum, Bochum, Germany, 1990."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/140952806"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300006082"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/100811970"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"P. Q. Nguyen and B. Vall\u00e9e (eds.),\n                      The LLL Algorithm: Survey and Applications\n                      , Springer, Berlin, 2010.","DOI":"10.1007\/978-3-642-02295-1"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"J. Oxley,\n                      Matroid Theory\n                      , 2nd ed., Oxford University Press, Oxford, UK, 2011.","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001"},{"key":"atypb30","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 1970."},{"key":"atypb31","unstructured":"A. Schrijver,\n                      Theory of Linear and Integer Programming\n                      , Wiley, Chichester, UK, 1986."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90075-1"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300008652"},{"key":"atypb34","unstructured":"K. Truemper,\n                      Matroid Decomposition\n                      , Academic Press, New York, 1992."},{"key":"atypb35","first-page":"144","volume":"88","author":"Tutte W. T.","year":"1958","journal-title":"Trans. Amer. Math. Soc."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.001"},{"key":"atypb37","unstructured":"W. T. Tutte,\n                      Introduction to the Theory of Matroids\n                      , Elsevier, New York, 1971."},{"key":"atypb38","unstructured":"F. Vallentin,\n                      \u00dcber die Paralleloeder-Vermutung von Vorono\u00ef\n                      . Diploma thesis, University of Dortmund, Dortmund, Germany, 2000."},{"key":"atypb39","unstructured":"F. Vallentin,\n                      Sphere Coverings, Lattices, and Tilings\n                      , Dissertation, Technische Universit\u00e4t M\u00fcnchen, Munich, Germany, 2003."},{"key":"atypb40","unstructured":"F. Vallentin,\n                      A Note on Space Tiling Zonotopes\n                      , preprint,https:\/\/arxiv.org\/abs\/math\/0402053, 2004."},{"key":"atypb41","unstructured":"D. J. A. Welsh,\n                      Matroid Theory\n                      , Academic Press, New York, 1976."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1382258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:12Z","timestamp":1787317572000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1382258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1382258"],"URL":"https:\/\/doi.org\/10.1137\/20m1382258","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}