{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T19:55:03Z","timestamp":1773086103687,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T00:00:00Z","timestamp":1713916800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T00:00:00Z","timestamp":1713916800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["805241-QIP"],"award-info":[{"award-number":["805241-QIP"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["185030"],"award-info":[{"award-number":["185030"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["207365"],"award-info":[{"award-number":["207365"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1651861"],"award-info":[{"award-number":["1651861"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,3]]},"abstract":"Abstract<\/jats:title>\n Approximate integer programming is the following: For a given convex body \n \n $$K \\subseteq {\\mathbb {R}}^n$$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n \u2286<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, either determine whether \n \n $$K \\cap {\\mathbb {Z}}^n$$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n \u2229<\/mml:mo>\n \n \n Z<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is empty, or find an integer point in the convex body \n \n $$2\\cdot (K - c) +c$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \u00b7<\/mml:mo>\n (<\/mml:mo>\n K<\/mml:mi>\n -<\/mml:mo>\n c<\/mml:mi>\n )<\/mml:mo>\n +<\/mml:mo>\n c<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> which is K<\/jats:italic>, scaled by 2 from its center of gravity c<\/jats:italic>. Approximate integer programming can be solved in time \n \n $$2^{O(n)}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> while the fastest known methods for exact integer programming run in time \n \n $$2^{O(n)} \\cdot n^n$$<\/jats:tex-math>\n \n \n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point \n \n $$x^* \\in (K \\cap {\\mathbb {Z}}^n)$$<\/jats:tex-math>\n \n \n \n x<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n \u2208<\/mml:mo>\n \n (<\/mml:mo>\n K<\/mml:mi>\n \u2229<\/mml:mo>\n \n \n Z<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> can be found in time \n \n $$2^{O(n)}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, provided that the remainders<\/jats:italic> of each component \n \n $$x_i^* \\mod \\ell $$<\/jats:tex-math>\n \n \n \n x<\/mml:mi>\n i<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msubsup>\n \n mod<\/mml:mo>\n \n \u2113<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> for some arbitrarily fixed \n \n $$\\ell \\ge 5(n+1)$$<\/jats:tex-math>\n \n \n \u2113<\/mml:mi>\n \u2265<\/mml:mo>\n 5<\/mml:mn>\n (<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of \n \n $$x^*$$<\/jats:tex-math>\n \n \n x<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> are given. The algorithm is based on a cutting-plane technique<\/jats:italic>, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a \n \n $$2^{O(n)}n^n$$<\/jats:tex-math>\n \n \n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \n n<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a new asymmetric approximate Carath\u00e9odory theorem<\/jats:italic> that might be of interest on its own. Our second method concerns integer programming problems in equation-standard form \n \n $$Ax = b, 0 \\le x \\le u, \\, x \\in {\\mathbb {Z}}^n$$<\/jats:tex-math>\n \n \n A<\/mml:mi>\n x<\/mml:mi>\n =<\/mml:mo>\n b<\/mml:mi>\n ,<\/mml:mo>\n 0<\/mml:mn>\n \u2264<\/mml:mo>\n x<\/mml:mi>\n \u2264<\/mml:mo>\n u<\/mml:mi>\n ,<\/mml:mo>\n \n x<\/mml:mi>\n \u2208<\/mml:mo>\n \n \n Z<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Such a problem can be reduced to the solution of \n \n $$\\prod _i O(\\log u_i +1)$$<\/jats:tex-math>\n \n \n \n \u220f<\/mml:mo>\n i<\/mml:mi>\n <\/mml:msub>\n O<\/mml:mi>\n \n (<\/mml:mo>\n log<\/mml:mo>\n \n u<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> approximate integer programming problems. This implies, for example that knapsack<\/jats:italic> or subset-sum<\/jats:italic> problems with polynomial variable range<\/jats:italic>\n \n \n $$0 \\le x_i \\le p(n)$$<\/jats:tex-math>\n \n \n 0<\/mml:mn>\n \u2264<\/mml:mo>\n \n x<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n \u2264<\/mml:mo>\n p<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> can be solved in time \n \n $$(\\log n)^{O(n)}$$<\/jats:tex-math>\n \n \n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. For these problems, the best running time so far was \n \n $$n^n \\cdot 2^{O(n)}$$<\/jats:tex-math>\n \n \n \n n<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s10107-024-02084-1","type":"journal-article","created":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T15:01:56Z","timestamp":1713970916000},"page":"223-241","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["From approximate to exact integer programming"],"prefix":"10.1007","volume":"210","author":[{"given":"Daniel","family":"Dadush","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedrich","family":"Eisenbrand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-8314-0963","authenticated-orcid":false,"given":"Thomas","family":"Rothvoss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,24]]},"reference":[{"key":"2084_CR1","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Algorithms and Combinatorics, vol. 2. Springer, New York (1988)"},{"key":"2084_CR2","series-title":"Handbooks in Operations Research and Management Science","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/S0927-0507(89)01007-8","volume-title":"Optimization","author":"GL Nemhauser","year":"1989","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer programming. In: Al, G.L.N. (ed.) Optimization. Handbooks in Operations Research and Management Science, vol. 1, pp. 447\u2013527. Elsevier, New York (1989)"},{"key":"2084_CR3","first-page":"1649","volume-title":"Handbook of combinatorics","author":"A Schrijver","year":"1995","unstructured":"Schrijver, A.: Polyhedral combinatorics. In: Graham, R., Gr\u00f6tschel, M., Lov\u00e1sz, L. (eds.) Handbook of combinatorics, pp. 1649\u20131704. Elsevier, New York (1995)"},{"issue":"4","key":"2084_CR4","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"2084_CR5","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"key":"2084_CR6","volume-title":"Integer programming, lattice algorithms, and deterministic","author":"D Dadush","year":"2012","unstructured":"Dadush, D.: Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta (2012)"},{"issue":"2","key":"2084_CR7","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/s00453-013-9834-8","volume":"70","author":"D Dadush","year":"2014","unstructured":"Dadush, D.: A randomized sieving algorithm for approximate integer programming. Algorithmica 70(2), 208\u2013244 (2014). https:\/\/doi.org\/10.1007\/s00453-013-9834-8","journal-title":"Algorithmica"},{"key":"2084_CR8","volume-title":"On convergence proofs for perceptrons","author":"AB Novikoff","year":"1963","unstructured":"Novikoff, A.B.: On convergence proofs for perceptrons. Technical report, Office of Naval Research, Washington, D.C. (1963)"},{"key":"2084_CR9","doi-asserted-by":"crossref","unstructured":"Barman, S.: Approximating nash equilibria and dense bipartite subgraphs via an approximate version of caratheodory\u2019s theorem. In: Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, pp. 361\u2013369 (2015)","DOI":"10.1145\/2746539.2746566"},{"key":"2084_CR10","unstructured":"Mirrokni, V., Leme, R.P., Vladu, A., Wong, S.C.-w.: Tight bounds for approximate carath\u00e9odory and beyond. In: International Conference on Machine Learning, pp. 2440\u20132448 (2017). PMLR"},{"key":"2084_CR11","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In: Proceedings of the Forty-second ACM Symposium on Theory of Computing, pp. 351\u2013358 (2010)","DOI":"10.1145\/1806689.1806739"},{"issue":"18","key":"2084_CR12","doi-asserted-by":"publisher","first-page":"1648","DOI":"10.1016\/j.tcs.2008.12.045","volume":"410","author":"J Bl\u00f6mer","year":"2009","unstructured":"Bl\u00f6mer, J., Naewe, S.: Sampling methods for shortest vectors, closest vectors and successive minima. Theor. Comput. Sci. 410(18), 1648\u20131665 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2008.12.045","journal-title":"Theor. Comput. Sci."},{"key":"2084_CR13","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, pp. 601\u2013610 (2001)","DOI":"10.1145\/380752.380857"},{"key":"2084_CR14","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., H\u00e4hnle, N., Niemeier, M.: Covering cubes and the closest vector problem. In: Proceedings of the Twenty-seventh Annual Symposium on Computational Geometry, pp. 417\u2013423 (2011)","DOI":"10.1145\/1998196.1998264"},{"issue":"1","key":"2084_CR15","first-page":"1","volume":"16","author":"F Eisenbrand","year":"2019","unstructured":"Eisenbrand, F., Weismantel, R.: Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Trans Algorithms (TALG) 16(1), 1\u201314 (2019)","journal-title":"ACM Trans Algorithms (TALG)"},{"key":"2084_CR16","unstructured":"Jansen, K., Rohwedder, L.: On integer programming and convolution. In: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) (2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"issue":"3","key":"2084_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3397484","volume":"12","author":"D Knop","year":"2020","unstructured":"Knop, D., Pilipczuk, M., Wrochna, M.: Tight complexity lower bounds for integer linear programming with few constraints. ACM Trans Comput Theory (TOCT) 12(3), 1\u201319 (2020)","journal-title":"ACM Trans Comput Theory (TOCT)"},{"issue":"3731","key":"2084_CR18","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1126\/science.153.3731.34","volume":"153","author":"R Bellman","year":"1966","unstructured":"Bellman, R.: Dynamic programming. Science 153(3731), 34\u201337 (1966)","journal-title":"Science"},{"key":"2084_CR19","doi-asserted-by":"crossref","unstructured":"Bringmann, K.: A near-linear pseudopolynomial time algorithm for subset sum. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1073\u20131084 (2017). SIAM","DOI":"10.1137\/1.9781611974782.69"},{"issue":"1","key":"2084_CR20","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1006\/jcta.1997.2780","volume":"79","author":"N Alon","year":"1997","unstructured":"Alon, N., V\u0169, V.H.: Anti-hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs. J Comb Theory, Series A 79(1), 133\u2013160 (1997)","journal-title":"J Comb Theory, Series A"},{"issue":"1","key":"2084_CR21","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"JC Lagarias","year":"1985","unstructured":"Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. J ACM (JACM) 32(1), 229\u2013246 (1985)","journal-title":"J ACM (JACM)"},{"key":"2084_CR22","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Mathematische annalen 261, 515\u2013534 (1982)","journal-title":"Mathematische annalen"},{"key":"2084_CR23","doi-asserted-by":"crossref","unstructured":"Reis, V., Rothvoss, T.: The subspace flatness conjecture and faster integer programming. In: FOCS, pp. 974\u2013988. IEEE, New York (2023)","DOI":"10.1109\/FOCS57990.2023.00060"},{"key":"2084_CR24","volume-title":"The Kluwer international series in engineering and computer science","author":"D Micciancio","year":"2002","unstructured":"Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems\u2013A Cryptograhic Perspective. In: The Kluwer international series in engineering and computer science, vol. 671. Springer, New York (2002)"},{"issue":"1","key":"2084_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"M Dyer","year":"1991","unstructured":"Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM 38(1), 1\u201317 (1991). https:\/\/doi.org\/10.1145\/102782.102783","journal-title":"J. ACM"},{"issue":"4","key":"2084_CR26","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1145\/1008731.1008733","volume":"51","author":"D Bertsimas","year":"2004","unstructured":"Bertsimas, D., Vempala, S.: Solving convex programs by random walks. J ACM (JACM) 51(4), 540\u2013556 (2004)","journal-title":"J ACM (JACM)"},{"key":"2084_CR27","doi-asserted-by":"publisher","unstructured":"Artstein-Avidan, S., Giannopoulos, A., Milman, V.D.: Asymptotic Geometric Analysis. Part I. Mathematical Surveys and Monographs, vol. 202, p. 451. American Mathematical Society, Providence, RI (2015). https:\/\/doi.org\/10.1090\/surv\/202","DOI":"10.1090\/surv\/202"},{"issue":"1","key":"2084_CR28","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49\u201365 (1987)","journal-title":"Combinatorica"},{"key":"2084_CR29","series-title":"Wiley-Interscience series in discrete mathematics and optimization","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1999","unstructured":"Schrijver, A.: Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization, Wiley, Hoboken (1999)"},{"key":"2084_CR30","first-page":"976","volume-title":"SODA","author":"H Jiang","year":"2021","unstructured":"Jiang, H.: Minimizing convex functions with integral minimizers. In: SODA, pp. 976\u2013985. SIAM, Philadelphia (2021)"},{"issue":"1","key":"2084_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X","volume":"11","author":"R Kannan","year":"1997","unstructured":"Kannan, R., Lov\u00e1sz, L., Simonovits, M.: Random walks and an o$${}^{\\text{* }}$$(n$${}^{\\text{5 }}$$) volume algorithm for convex bodies. Random Struct. Algorithms 11(1), 1\u201350 (1997)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"2084_CR32","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1090\/S0894-0347-09-00650-X","volume":"23","author":"R Adamczak","year":"2010","unstructured":"Adamczak, R., Litvak, A.E., Pajor, A., Tomczak-Jaegermann, N.: Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles. J. Amer. Math. Soc. 23(2), 535\u2013561 (2010). https:\/\/doi.org\/10.1090\/S0894-0347-09-00650-X","journal-title":"J. Amer. Math. Soc."},{"key":"2084_CR33","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: STOC, pp. 601\u2013610. ACM, New York (2001)","DOI":"10.1145\/380752.380857"},{"issue":"1","key":"2084_CR34","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/BF01191202","volume":"12","author":"W Cook","year":"1992","unstructured":"Cook, W., Hartmann, M., Kannan, R., McDiarmid, C.: On integer points in polyhedra. Combinatorica 12(1), 27\u201337 (1992)","journal-title":"Combinatorica"},{"key":"2084_CR35","unstructured":"Polak, A., Rohwedder, L., Wegrzycki, K.: Knapsack and subset sum with small items. In: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp. 106\u20131 (2021). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02084-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02084-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02084-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T15:49:15Z","timestamp":1740757755000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02084-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,24]]},"references-count":35,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["2084"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02084-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,24]]},"assertion":[{"value":"27 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}