{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T08:06:41Z","timestamp":1768637201232,"version":"3.49.0"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T00:00:00Z","timestamp":1705708800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T00:00:00Z","timestamp":1705708800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100010653","name":"Masarykova Univerzita","doi-asserted-by":"publisher","award":["MUNI\/I\/1677\/2018"],"award-info":[{"award-number":["MUNI\/I\/1677\/2018"]}],"id":[{"id":"10.13039\/501100010653","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["648509"],"award-info":[{"award-number":["648509"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["BEETHOVEN; UMO-2018\/31\/G\/ST1\/03718"],"award-info":[{"award-number":["BEETHOVEN; UMO-2018\/31\/G\/ST1\/03718"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["MUNI\/I\/1677\/2018"],"award-info":[{"award-number":["MUNI\/I\/1677\/2018"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix <jats:italic>A<\/jats:italic> and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of <jats:italic>A<\/jats:italic>, and when parameterized by the dual tree-depth and the entry complexity of <jats:italic>A<\/jats:italic>; both these parameterization imply that <jats:italic>A<\/jats:italic> is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-norm of the Graver basis is bounded by a function of the maximum <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-norm of a circuit of <jats:italic>A<\/jats:italic>. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix <jats:italic>A<\/jats:italic> that has small primal\/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-norm of the Graver basis of the constraint matrix, when parameterized by the <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix.<\/jats:p>","DOI":"10.1007\/s10107-023-02048-x","type":"journal-article","created":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T10:02:28Z","timestamp":1705744948000},"page":"497-531","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming"],"prefix":"10.1007","volume":"208","author":[{"given":"Marcin","family":"Bria\u0144ski","sequence":"first","affiliation":[]},{"given":"Martin","family":"Kouteck\u00fd","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Kr\u00e1l\u2019","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3539-6431","authenticated-orcid":false,"given":"Krist\u00fdna","family":"Pek\u00e1rkov\u00e1","sequence":"additional","affiliation":[]},{"given":"Felix","family":"Schr\u00f6der","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,1,20]]},"reference":[{"issue":"2","key":"2048_CR1","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s10208-005-0174-1","volume":"7","author":"M Aschenbrenner","year":"2007","unstructured":"Aschenbrenner, M., Hemmecke, R.: Finiteness theorems in stochastic integer programming. Found. Comput. Math. 7(2), 183\u2013227 (2007)","journal-title":"Found. Comput. Math."},{"issue":"6","key":"2048_CR2","doi-asserted-by":"publisher","first-page":"1860","DOI":"10.1137\/S1064827502401953","volume":"25","author":"C Aykanat","year":"2004","unstructured":"Aykanat, C., Pinar, A., \u00c7ataly\u00fcrek, \u00dc.V.: Permuting sparse rectangular matrices into block-diagonal form. SIAM J. Sci. Comput. 25(6), 1860\u20131879 (2004)","journal-title":"SIAM J. Sci. Comput."},{"issue":"1\u20132","key":"2048_CR3","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s10107-014-0761-5","volume":"149","author":"M Bergner","year":"2015","unstructured":"Bergner, M., Caprara, A., Ceselli, A., Furini, F., L\u00fcbbecke, M.E., Malaguti, E., Traversi, E.: Automatic Dantzig\u2013Wolfe reformulation of mixed integer programs. Math. Program. 149(1\u20132), 391\u2013424 (2015)","journal-title":"Math. Program."},{"issue":"1","key":"2048_CR4","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1137\/S1052623497318682","volume":"9","author":"R Bornd\u00f6rfer","year":"1998","unstructured":"Bornd\u00f6rfer, R., Ferreira, C.E., Martin, A.: Decomposing matrices into blocks. SIAM J. Optim. 9(1), 236\u2013269 (1998)","journal-title":"SIAM J. Optim."},{"issue":"14","key":"2048_CR5","first-page":"12249","volume":"35","author":"C Brand","year":"2021","unstructured":"Brand, C., Kouteck\u00fd, M., Ordyniak, S.: Parameterized algorithms for MILPs with small treedepth. Proc. AAAI Conf. Artif. Intell. 35(14), 12249\u201312257 (2021)","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"2048_CR6","unstructured":"Bredereck, R., Figiel, A., Kaczmarczyk, A., Knop, D., Niedermeier, R.: High-multiplicity fair allocation made more practical. In: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS\u201921, pp. 260\u2013268. International Foundation for Autonomous Agents and Multiagent Systems (2021)"},{"key":"2048_CR7","doi-asserted-by":"crossref","unstructured":"Bredereck, R., Kaczmarczyk, A., Knop, D., Niedermeier, R.: High-multiplicity fair allocation: Lenstra empowered by n-fold integer programming. In: Proceedings of the 2019 ACM Conference on Economics and Computation, EC\u201919, pp. 505\u2013523. Association for Computing Machinery (2019)","DOI":"10.1145\/3328526.3329649"},{"key":"2048_CR8","unstructured":"Chan, T.F.N., Cooper, J.W., Kouteck\u00fd, M., Kr\u00e1l\u2019, D., Pek\u00e1rkov\u00e1, K.: Matrices of optimal tree-depth and row-invariant parameterized algorithm for integer programming. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 168, pp. 26:1\u201326:19 (2020)"},{"issue":"3","key":"2048_CR9","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1137\/20M1353502","volume":"51","author":"TFN Chan","year":"2022","unstructured":"Chan, T.F.N., Cooper, J.W., Kouteck\u00fd, M., Kr\u00e1l\u2019, D., Pek\u00e1rkov\u00e1, K.: Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming. SIAM J. Comput. 51(3), 664\u2013700 (2022)","journal-title":"SIAM J. Comput."},{"key":"2048_CR10","unstructured":"Chen, H., Chen, L., Zhang, G.: FPT algorithms for a special block-structured integer program with applications in scheduling. preprint arXiv:2107.01373 (2021)"},{"key":"2048_CR11","doi-asserted-by":"crossref","unstructured":"Chen, L., Marx, D.: Covering a tree with rooted subtrees\u2013parameterized and approximation algorithms. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 2801\u20132820. SIAM (2018)","DOI":"10.1137\/1.9781611975031.178"},{"key":"2048_CR12","doi-asserted-by":"crossref","unstructured":"Cslovjecsek, J., Eisenbrand, F., Hunkenschr\u00f6der, C., Rohwedder, L., Weismantel, R.: Block-structured integer and linear programming in strongly polynomial and near linear time. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pp. 1666\u20131681. SIAM (2021)","DOI":"10.1137\/1.9781611976465.101"},{"key":"2048_CR13","unstructured":"Cslovjecsek, J., Eisenbrand, F., Pilipczuk, M., Venzin, M., Weismantel, R.: Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity. In: 29th Annual European Symposium on Algorithms (ESA 2021), Leibniz International Proceedings in Informatics (LIPIcs), vol. 204, pp. 33:1\u201333:14 (2021)"},{"key":"2048_CR14","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, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"2","key":"2048_CR15","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.disopt.2006.06.006","volume":"5","author":"JA De Loera","year":"2008","unstructured":"De Loera, J.A., Hemmecke, R., Onn, S., Weismantel, R.: $${N}$$-fold integer programming. Discret. Optim. 5(2), 231\u2013241 (2008)","journal-title":"Discret. Optim."},{"key":"2048_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103186","volume":"90","author":"M DeVos","year":"2020","unstructured":"DeVos, M., Kwon, O., Oum, S.: Branch-depth: Generalizing tree-depth of graphs. Eur. J. Comb. 90, 103186 (2020)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"2048_CR17","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1006\/jctb.1995.1003","volume":"63","author":"G Ding","year":"1995","unstructured":"Ding, G., Oporowski, B., Oxley, J.: On infinite antichains of matroids. J. Comb. Theory Ser. B 63(1), 21\u201340 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"2048_CR18","doi-asserted-by":"crossref","unstructured":"Eiben, E., Ganian, R., Knop, D., Ordyniak, S., Pilipczuk, M., Wrochna, M.: Integer programming and incidence tree depth. In: Integer Programming and Combinatorial Optimization\u201420th International Conference (IPCO), LNCS vol. 11480, pp. 194\u2013204. Springer International Publishing (2019)","DOI":"10.1007\/978-3-030-17953-3_15"},{"key":"2048_CR19","unstructured":"Eisenbrand, F., Hunkenschr\u00f6der, C., Klein, K.: Faster algorithms for integer programs with block structure. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Leibniz International Proceedings in Informatics (LIPIcs), pp. 49:1\u201349:13 (2018)"},{"key":"2048_CR20","unstructured":"Eisenbrand, F., Hunkenschr\u00f6der, C., Klein, K., Kouteck\u00fd, M., Levin, A., Onn, S.: An algorithmic theory of integer programming. preprint arXiv:1904.01361 (2019)"},{"key":"2048_CR21","unstructured":"Ekbatani, F., Natura, B., V\u00e9gh, L.A.: Circuit imbalance measures and linear programming. preprint arXiv:2108.03616 (2021)"},{"issue":"1","key":"2048_CR22","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF01582130","volume":"80","author":"MC Ferris","year":"1998","unstructured":"Ferris, M.C., Horn, J.D.: Partitioning mathematical programs for parallel solution. Math. Program. 80(1), 35\u201361 (1998)","journal-title":"Math. Program."},{"key":"2048_CR23","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-642-13193-6_21","volume":"6049","author":"G Gamrath","year":"2010","unstructured":"Gamrath, G., L\u00fcbbecke, M.E.: Experiments with a generic Dantzig\u2013Wolfe decomposition for integer programs. Exp. Algorithms 6049, 239\u2013252 (2010)","journal-title":"Exp. Algorithms"},{"key":"2048_CR24","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.artint.2017.12.006","volume":"257","author":"R Ganian","year":"2018","unstructured":"Ganian, R., Ordyniak, S.: The complexity landscape of decompositional parameters for ILP. Artif. Intell. 257, 61\u201371 (2018)","journal-title":"Artif. Intell."},{"key":"2048_CR25","series-title":"Undergraduate Texts in Mathematics","volume-title":"Finite-Dimensional Vector Spaces","author":"P Halmos","year":"1993","unstructured":"Halmos, P.: Finite-Dimensional Vector Spaces. Undergraduate Texts in Mathematics, Springer, Berlin (1993)"},{"key":"2048_CR26","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10107-011-0490-y","volume":"137","author":"R Hemmecke","year":"2013","unstructured":"Hemmecke, R., Onn, S., Romanchuk, L.: $${N}$$-fold integer programming in cubic time. Math. Program. 137, 325\u2013341 (2013)","journal-title":"Math. Program."},{"key":"2048_CR27","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s10107-002-0322-1","volume":"94","author":"R Hemmecke","year":"2003","unstructured":"Hemmecke, R., Schultz, R.: Decomposition of test sets in stochastic integer programming. Math. Program. 94, 323\u2013341 (2003)","journal-title":"Math. Program."},{"key":"2048_CR28","unstructured":"Hermelin, D., Molter, H., Niedermeier, R., Shabtay, D.: Equitable scheduling for the total completion time objective. preprint arXiv:2112.13824 (2021)"},{"key":"2048_CR29","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd, P.: Branch-width, parse trees, and monadic second-order logic for matroids. In: H.\u00a0Alt, M.\u00a0Habib (eds.) 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), LNCS, vol. 2607, pp. 319\u2013330 (2003)","DOI":"10.1007\/3-540-36494-3_29"},{"issue":"3","key":"2048_CR30","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2005.08.005","volume":"96","author":"P Hlin\u011bn\u00fd","year":"2006","unstructured":"Hlin\u011bn\u00fd, P.: Branch-width, parse trees, and monadic second-order logic for matroids. J. Comb. Theory Ser. B 96(3), 325\u2013351 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"key":"2048_CR31","doi-asserted-by":"crossref","unstructured":"Jansen, K., Klein, K., Lassota, A.: The double exponential runtime is tight for 2-stage stochastic ILPs. In: M.\u00a0Singh, D.P. Williamson (eds.) Integer Programming and Combinatorial Optimization\u201422nd International Conference (IPCO), LNCS vol. 12707, Lecture Notes in Computer Science, vol. 12707, pp. 297\u2013310. Springer (2021)","DOI":"10.1007\/978-3-030-73879-2_21"},{"key":"2048_CR32","doi-asserted-by":"crossref","unstructured":"Jansen, K., Klein, K., Maack, M., Rau, M.: Empowering the configuration-IP: new PTAS results for scheduling with setup times. Math. Program. (2021)","DOI":"10.1007\/s10107-021-01694-3"},{"key":"2048_CR33","doi-asserted-by":"crossref","unstructured":"Jansen, K., Lassota, A., Maack, M.: Approximation algorithms for scheduling with class constraints. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 349\u2013357. Association for Computing Machinery (2020)","DOI":"10.1145\/3350755.3400247"},{"issue":"4","key":"2048_CR34","doi-asserted-by":"publisher","first-page":"2282","DOI":"10.1137\/19M1303873","volume":"34","author":"K Jansen","year":"2020","unstructured":"Jansen, K., Lassota, A., Rohwedder, L.: Near-linear time algorithm for $$n$$-fold ILPs via color coding. SIAM J. Discret. Math. 34(4), 2282\u20132299 (2020)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"2048_CR35","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":"2048_CR36","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.ejc.2016.08.005","volume":"59","author":"F Kardo\u0161","year":"2017","unstructured":"Kardo\u0161, F., Kr\u00e1l\u2019, D., Liebenau, A., Mach, L.: First order convergence of matroids. Eur. J. Comb. 59, 150\u2013168 (2017)","journal-title":"Eur. J. Comb."},{"key":"2048_CR37","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103. Springer, Berlin (1972)"},{"issue":"3","key":"2048_CR38","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1287\/ijoc.2017.0797","volume":"30","author":"T Khaniyev","year":"2018","unstructured":"Khaniyev, T., Elhedhli, S., Erenay, F.S.: Structure detection in mixed-integer programs. INFORMS J. Comput. 30(3), 570\u2013587 (2018)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"2048_CR39","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10107-021-01698-z","volume":"192","author":"K Klein","year":"2022","unstructured":"Klein, K.: About the complexity of two-stage stochastic IPs. Math. Program. 192(1), 319\u2013337 (2022)","journal-title":"Math. Program."},{"key":"2048_CR40","doi-asserted-by":"crossref","unstructured":"Klein, K., Reuter, J.: Collapsing the tower\u2014on the complexity of multistage stochastic IPs. In: 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pp. 348\u2013358. SIAM (2022)","DOI":"10.1137\/1.9781611977073.17"},{"key":"2048_CR41","unstructured":"Knop, D., Kouteck\u00fd, M.: Scheduling kernels via configuration LP. preprint arXiv:2003.02187 (2018)"},{"issue":"5","key":"2048_CR42","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s10951-017-0550-0","volume":"21","author":"D Knop","year":"2018","unstructured":"Knop, D., Kouteck\u00fd, M.: Scheduling meets $$n$$-fold integer programming. J. Sched. 21(5), 493\u2013503 (2018)","journal-title":"J. Sched."},{"key":"2048_CR43","unstructured":"Knop, D., Kouteck\u00fd, M., Mnich, M.: Combinatorial n-fold integer programming and applications. In: 25th Annual European Symposium on Algorithms (ESA), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a087, pp. 54:1\u201354:14 (2017)"},{"key":"2048_CR44","unstructured":"Kouteck\u00fd, M., Levin, A., Onn, S.: A parameterized strongly polynomial algorithm for block structured integer programs. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 107, pp. 85:1\u201385:14 (2018)"},{"issue":"4","key":"2048_CR45","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."},{"key":"2048_CR46","series-title":"Oxford Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001","volume-title":"Matroid Theory","author":"J Oxley","year":"2011","unstructured":"Oxley, J.: Matroid Theory. Oxford Graduate Texts in Mathematics, Oxford University Press, Oxford (2011)"},{"key":"2048_CR47","unstructured":"Pothen, A.: The complexity of optimal elimination trees. Technical Report CS-88-13, Pennsylvania State University (1988)"},{"key":"2048_CR48","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF02680560","volume":"83","author":"R Schultz","year":"1998","unstructured":"Schultz, R., Stougie, L., van der Vlerk, M.H.: Solving stochastic programs with integer recourse by enumeration: a framework using gr\u00f6bner basis reductions. Math. Program. 83, 229\u2013252 (1998)","journal-title":"Math. Program."},{"key":"2048_CR49","doi-asserted-by":"crossref","unstructured":"Vanderbeck, F., Wolsey, L.A.: Reformulation and decomposition of integer programs. In: 50 Years of Integer Programming 1958\u20132008, pp. 431\u2013502. Springer (2010)","DOI":"10.1007\/978-3-540-68279-0_13"},{"key":"2048_CR50","doi-asserted-by":"crossref","unstructured":"Wang, J., Ralphs, T.: Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pp. 394\u2013402. Springer (2013)","DOI":"10.1007\/978-3-642-38171-3_31"},{"issue":"1","key":"2048_CR51","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1287\/mnsc.18.1.98","volume":"18","author":"RL Weil","year":"1971","unstructured":"Weil, R.L., Kettler, P.C.: Rearranging matrices to block-angular form for decomposition (and other) algorithms. Manag. Sci. 18(1), 98\u2013108 (1971)","journal-title":"Manag. Sci."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02048-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02048-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02048-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T16:10:54Z","timestamp":1729008654000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02048-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,20]]},"references-count":51,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["2048"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02048-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,20]]},"assertion":[{"value":"5 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}