{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:20:58Z","timestamp":1787322058384,"version":"build-2736575974"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We prove a representation theorem of projections of sets of integer points by an integer matrix $W$. Our result can be seen as a polyhedral analogue of several classical and recent results related to the Frobenius problem. Our result is motivated by a large class of nonlinear integer optimization problems in variable dimension. Concretely, we aim to optimize $f(Wx)$ over a set $\\mathcal{F} = P\\cap \\mathbb{Z}^n$, where $f$ is a nonlinear function, $P\\subset \\mathbb{R}^n$ is a polyhedron, and $W\\in \\mathbb{Z}^{d\\times n}$. As a consequence of our representation theorem, we obtain a general efficient transformation from the latter class of problems to integer linear programming. Our bounds depend polynomially on various important parameters of the input data leading, among others, to first polynomial time algorithms for several classes of nonlinear optimization problems.<\/jats:p>","DOI":"10.1137\/14m0973694","type":"journal-article","created":{"date-parts":[[2015,7,30]],"date-time":"2015-07-30T15:34:34Z","timestamp":1438270474000},"page":"1287-1302","source":"Crossref","is-referenced-by-count":3,"title":["A Polyhedral Frobenius Theorem with Applications to Integer Optimization"],"prefix":"10.1137","volume":"29","author":[{"given":"David","family":"Adjiashvili","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Timm","family":"Oertel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Weismantel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,7,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/090778043"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.2307\/2371684"},{"key":"atypb3","first-page":"215","volume":"211","author":"Brauer A.","year":"1962","journal-title":"J. Reine Angew. Math."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0169"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.06.006"},{"key":"atypb6","unstructured":"A. Del Pia, R. Hildebrand, R. Weismantel, and K. Zemmer,\n                      Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane\n                      , preprint, arXiv:1408.4711 [math.OC], 2014."},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"A. Del Pia and R. Weismantel,\n                      Integer quadratic programming in the plane\n                      , in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 2014, pp. 840-846.","DOI":"10.1137\/1.9781611973402.62"},{"key":"atypb8","unstructured":"F. Eisenbrand, S. Vempala, and R. Weismantel,\n                      Revisiting Dynamic Programming for Integer Optimization\n                      , 2014."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.4064\/aa-21-1-399-408"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"M. Gro\u0308tschel, L. Lova\u0301sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Algorithms Combin. 2, Springer-Verlag, Berlin, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"atypb11","unstructured":"P. M. Gruber,\n                      Convex and Discrete Geometry\n                      , Grundlehren Math. Wiss. 336, Springer-Verlag, Berlin, 2007."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/96559.96597"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"R. Kannan,\n                      Solution of the Frobenius Problem and Its Generalization\n                      , manuscript, 1989.","DOI":"10.1007\/3-540-52048-1_47"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01204720"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01442795"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02128669"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01300131"},{"key":"atypb18","unstructured":"A. Schrijver,\n                      Theory of Linear and Integer Programming\n                      , Wiley-Interscience Ser. in Discrete Math., John Wiley, Chichester, UK, 1986."},{"key":"atypb19","unstructured":"A. Sebo\u0308, Hilbert bases, Caratheodory's theorem, and combinatorial optimization, in Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, University of Waterloo Press, 1990, pp. 431-455."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/14M0973694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:17:41Z","timestamp":1787318261000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/14M0973694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/14M0973694"],"URL":"https:\/\/doi.org\/10.1137\/14m0973694","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}