{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T00:57:41Z","timestamp":1768352261454,"version":"3.49.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,2,17]],"date-time":"2018-02-17T00:00:00Z","timestamp":1518825600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["14-41-00039"],"award-info":[{"award-number":["14-41-00039"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["17-11-01336"],"award-info":[{"award-number":["17-11-01336"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Russian President Grant","award":["MD-487.2018.1"],"award-info":[{"award-number":["MD-487.2018.1"]}]},{"DOI":"10.13039\/501100002261","name":"Russian Foundation for Basic Research","doi-asserted-by":"publisher","award":["16-31-60008-mol-a-dk"],"award-info":[{"award-number":["16-31-60008-mol-a-dk"]}],"id":[{"id":"10.13039\/501100002261","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s10878-018-0264-z","type":"journal-article","created":{"date-parts":[[2018,2,17]],"date-time":"2018-02-17T02:16:18Z","timestamp":1518833778000},"page":"1128-1146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["FPT-algorithms for some problems related to integer programming"],"prefix":"10.1007","volume":"35","author":[{"given":"D. V.","family":"Gribanov","sequence":"first","affiliation":[]},{"given":"D. S.","family":"Malyshev","sequence":"additional","affiliation":[]},{"given":"P. M.","family":"Pardalos","sequence":"additional","affiliation":[]},{"given":"S. I.","family":"Veselov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,2,17]]},"reference":[{"key":"264_CR1","unstructured":"Ajtai M (1996) Generating hard instances of lattice problems. In: Proceedings of 28th annual ACM symposium on the theory of computing, pp 99\u2013108"},{"key":"264_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai M, Kumar R, Sivakumar D (2001) A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the 33rd annual ACM symposium on theory of computing, pp 601\u2013610","DOI":"10.1145\/380752.380857"},{"key":"264_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai M, Kumar R, Sivakumar D (2002) Sampling short lattice vectors and the closest lattice vector problem. In: Proceedings of 17th IEEE annual conference on computational complexity, pp 53\u201357","DOI":"10.1109\/CCC.2002.1004339"},{"key":"264_CR4","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1134\/S1990478911010029","volume":"5","author":"VV Alekseev","year":"2011","unstructured":"Alekseev VV, Zakharova D (2011) Independent sets in the graphs with bounded minors of the extended incidence matrix. J Appl Ind Math 5:14\u201318","journal-title":"J Appl Ind Math"},{"issue":"5","key":"264_CR5","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1016\/j.orl.2016.07.004","volume":"44","author":"S Artmann","year":"2016","unstructured":"Artmann S, Eisenbrand F, Glanzer C, Timm O, Vempala S, Weismantel R (2016) A note on non-degenerate integer programs with small subdeterminants. Oper Res Lett 44(5):635\u2013639","journal-title":"Oper Res Lett"},{"key":"264_CR6","doi-asserted-by":"crossref","unstructured":"Artmann S, Weismantel R, Zenklusen R (2017) A strongly polynomial algorithm for bimodular integer linear programming. In: Proceedings of 49th annual ACM symposium on theory of computing, pp 1206\u20131219","DOI":"10.1145\/3055399.3055473"},{"issue":"18","key":"264_CR7","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 (2009) Sampling methods for shortest vectors, closest vectors and successive minima. Theor Comput Sci 410(18):1648\u20131665","journal-title":"Theor Comput Sci"},{"key":"264_CR8","unstructured":"Bock A, Faenza Y, Moldenhauer C, Vargas R, Jacinto A (2014) Solving the stable set problem in terms of the odd cycle packing number. In: Proceedings of 34th annual conference on foundations of software technology and theoretical computer science, pp 187\u2013198"},{"issue":"1","key":"264_CR9","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/s00454-014-9601-x","volume":"52","author":"N Bonifas","year":"2014","unstructured":"Bonifas N, Di Summa M, Eisenbrand F, H\u00e4hnle N, Niemeier M (2014) On subdeterminants and the diameter of polyhedra. Discrete Computat Geom 52(1):102\u2013115","journal-title":"Discrete Computat Geom"},{"key":"264_CR10","volume-title":"An introduction to the geometry of numbers","author":"JWS Cassels","year":"1971","unstructured":"Cassels JWS (1971) An introduction to the geometry of numbers, 2nd edn. Springer, Berlin","edition":"2"},{"key":"264_CR11","unstructured":"Cheon JH, Lee C (2015) Approximate algorithms on lattices with small determinant. Cryptology ePrint Archive, Report 2015\/461. \n                    http:\/\/eprint.iacr.org\/2015\/461"},{"key":"264_CR12","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01582230","volume":"34","author":"W Cook","year":"1986","unstructured":"Cook W, Gerards AMH, Schrijver A, Tardos E (1986) Sensitivity theorems in integer linear programming. Math Program 34:251\u2013264","journal-title":"Math Program"},{"key":"264_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer, Berlin"},{"key":"264_CR14","doi-asserted-by":"crossref","unstructured":"Dadush D, Peikert C, Vempala S (2011) Enumerative algorithms for the shortest and closest lattice vector problems in any norm via M-ellipsoid coverings. In: 52nd IEEE annual symposium on foundations of computer science, pp 580\u2013589","DOI":"10.1109\/FOCS.2011.31"},{"key":"264_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1999","unstructured":"Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin"},{"key":"264_CR16","unstructured":"Eisenbrand F, Vempala S (2016) Geometric random edge. \n                    arXiv:1404.1568v5"},{"key":"264_CR17","doi-asserted-by":"crossref","unstructured":"Eisenbrand F, H\u00e4hnle N, Niemeier M (2011) Covering cubes and the closest vector problem. In: Proceedings of 27th annual symposium on computational geometry, pp 417\u2013423","DOI":"10.1145\/1998196.1998264"},{"key":"264_CR18","doi-asserted-by":"crossref","unstructured":"Fincke U, Pohst M (1983) A procedure for determining algebraic integers of given norm. Lecture Notes in Computer Science, vol 162, pp 194\u2013202","DOI":"10.1007\/3-540-12868-9_103"},{"issue":"170","key":"264_CR19","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1090\/S0025-5718-1985-0777278-8","volume":"44","author":"U Fincke","year":"1985","unstructured":"Fincke U, Pohst M (1985) Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math Comput 44(170):463\u2013471","journal-title":"Math Comput"},{"issue":"2","key":"264_CR20","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1073\/pnas.53.2.260","volume":"53","author":"RE Gomory","year":"1965","unstructured":"Gomory RE (1965) On the relation between integer and non-integer solutions to linear programs. Proc Natl Acad Sci USA 53(2):260\u2013265","journal-title":"Proc Natl Acad Sci USA"},{"key":"264_CR21","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-319-09758-9_4","volume":"104","author":"DV Gribanov","year":"2013","unstructured":"Gribanov DV (2013) The flatness theorem for some class of polytopes and searching an integer point. Springer Proc Math Stat 104:37\u201345","journal-title":"Springer Proc Math Stat"},{"issue":"6","key":"264_CR22","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1007\/s11590-016-1048-y","volume":"10","author":"DV Gribanov","year":"2016","unstructured":"Gribanov DV, Chirkov AJ (2016) The width and integer optimization on simplices with bounded minors of the constraint matrices. Optim Lett 10(6):1179\u20131189","journal-title":"Optim Lett"},{"key":"264_CR23","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.dam.2017.04.025","volume":"227","author":"DV Gribanov","year":"2017","unstructured":"Gribanov DV, Malyshev DS (2017) The computational complexity of three graph problems for instances with bounded minors of constraint matrices. Discrete Appl Math 227:13\u201320","journal-title":"Discrete Appl Math"},{"issue":"6","key":"264_CR24","doi-asserted-by":"publisher","first-page":"1169","DOI":"10.1007\/s11590-015-0943-y","volume":"10","author":"DV Gribanov","year":"2016","unstructured":"Gribanov DV, Veselov SI (2016) On integer programming with bounded determinants. Optim Lett 10(6):1169\u20131177","journal-title":"Optim Lett"},{"key":"264_CR25","volume-title":"Geometry of numbers","author":"M Gruber","year":"1987","unstructured":"Gruber M, Lekkerkerker CG (1987) Geometry of numbers. North-Holland, Amsterdam"},{"key":"264_CR26","doi-asserted-by":"crossref","unstructured":"Hanrot G, Pujol X, Stehle D (2011) Algorithms for the shortest and closest lattice vector problems. Lecture Notes in Computer Science, vol 6639, pp 159\u2013190","DOI":"10.1007\/978-3-642-20901-7_10"},{"key":"264_CR27","volume-title":"Integer programming and network flows","author":"TC Hu","year":"1970","unstructured":"Hu TC (1970) Integer programming and network flows. Addison-Wesley, Reading"},{"key":"264_CR28","doi-asserted-by":"crossref","unstructured":"Kannan R (1983) Improved algorithms for integer programming and related lattice problems. In: Proceedings of 15th annual ACM symposium on theory of computing, pp 99\u2013108","DOI":"10.1145\/800061.808749"},{"issue":"3","key":"264_CR29","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan R (1987) Minkowski\u2019s convex body theorem and integer programming. Math Oper Res 12(3):415\u2013440","journal-title":"Math Oper Res"},{"issue":"4","key":"264_CR30","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar N (1984) A new polynomial time algorithm for linear programming. Combinatorica 4(4):373\u2013391","journal-title":"Combinatorica"},{"issue":"1","key":"264_CR31","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"LG Khachiyan","year":"1980","unstructured":"Khachiyan LG (1980) Polynomial algorithms in linear programming. Comput Math Math Phys 20(1):53\u201372","journal-title":"Comput Math Math Phys"},{"issue":"4","key":"264_CR32","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra HW (1983) Integer programming with a fixed number of variables. Math Oper Res 8(4):538\u2013548","journal-title":"Math Oper Res"},{"key":"264_CR33","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra AK, Lenstra HW Jr, Lovasz L (1982) Factoring polynomials with rational coefficients. Math Ann 261:515\u2013534","journal-title":"Math Ann"},{"key":"264_CR34","doi-asserted-by":"crossref","unstructured":"Micciancio D, Voulgaris P (2010) A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: Proceedings of 42nd annual ACM symposium on theory of computing, pp 351\u2013358","DOI":"10.1145\/1806689.1806739"},{"key":"264_CR35","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791","volume-title":"Interior point polynomial methods in convex programming","author":"YE Nesterov","year":"1994","unstructured":"Nesterov YE, Nemirovsky AS (1994) Interior point polynomial methods in convex programming. Society for Industrial and Applied Mathematics, Philadelphia"},{"key":"264_CR36","first-page":"45","volume":"19","author":"PM Pardalos","year":"1991","unstructured":"Pardalos PM, Han CG, Ye Y (1991) Interior point algorithms for solving nonlinear optimization problems. COAL Newsl 19:45\u201354","journal-title":"COAL Newsl"},{"key":"264_CR37","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver A (1998) Theory of linear and integer programming. Wiley, London"},{"key":"264_CR38","doi-asserted-by":"crossref","unstructured":"Seb\u00f6 A (1999) An introduction to empty lattice simplicies. Lecture Notes in Computer Science, vol 1610, pp 400\u2013414","DOI":"10.1007\/3-540-48777-8_30"},{"key":"264_CR39","doi-asserted-by":"publisher","DOI":"10.1090\/mmono\/156","volume-title":"Qualitative topics in integer linear programming (translations of mathematical monographs)","author":"VN Shevchenko","year":"1996","unstructured":"Shevchenko VN (1996) Qualitative topics in integer linear programming (translations of mathematical monographs). AMS Book, Providence"},{"key":"264_CR40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-08287-4","volume-title":"Lectures on the geometry of numbers","author":"CL Siegel","year":"1989","unstructured":"Siegel CL (1989) Lectures on the geometry of numbers. Springer, Berlin"},{"key":"264_CR41","doi-asserted-by":"crossref","unstructured":"Storjohann A (1996) Near optimal algorithms for computing Smith normal forms of integer matrices. In: Proceedings of the 1996 international symposium on symbolic and algebraic computation, pp 267\u2013274","DOI":"10.1145\/236869.237084"},{"key":"264_CR42","doi-asserted-by":"crossref","unstructured":"Storjohann A, Labahn G (1996) Asymptotically fast computation of Hermite normal forms of integer matrices. In: Proceedings of the 1996 international symposium on symbolic and algebraic computation, pp 259\u2013266","DOI":"10.1145\/236869.237083"},{"issue":"2","key":"264_CR43","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E Tardos","year":"1986","unstructured":"Tardos E (1986) A strongly polynomial algorithm to solve combinatorial linear programs. Oper Res 34(2):250\u2013256","journal-title":"Oper Res"},{"issue":"2","key":"264_CR44","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.disopt.2008.12.002","volume":"6","author":"SI Veselov","year":"2009","unstructured":"Veselov SI, Chirkov AJ (2009) Integer program with bimodular matrix. Discrete Optim 6(2):220\u2013222","journal-title":"Discrete Optim"},{"key":"264_CR45","volume-title":"Computing the Smith forms of integer matrices and solving related problems","author":"W Zhendong","year":"2005","unstructured":"Zhendong W (2005) Computing the Smith forms of integer matrices and solving related problems. University of Delaware, Newark"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0264-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0264-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0264-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T22:16:05Z","timestamp":1550355365000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0264-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,17]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["264"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0264-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,17]]},"assertion":[{"value":"17 February 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}