{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:58:03Z","timestamp":1781305083982,"version":"3.54.1"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-28691-8_12","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:33:43Z","timestamp":1781303623000},"page":"173-187","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Solving\u00a04-Block Integer Linear Programs Faster Using\u00a0Affine\u00a0Decompositions of\u00a0the\u00a0Right-Hand\u00a0Sides"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6215-066X","authenticated-orcid":false,"given":"Alexandra","family":"Lassota","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-6823-5225","authenticated-orcid":false,"given":"Koen","family":"Ligthart","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","unstructured":"Bach, E., Eisenbrand, F., Rothvoss, T., Weismantel, R.: Forall-exist statements in pseudopolynomial time. In: Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2225\u20132233 (2025). https:\/\/doi.org\/10.1137\/1.9781611978322.73","DOI":"10.1137\/1.9781611978322.73"},{"issue":"2","key":"12_CR2","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00303169","volume":"6","author":"J Bartholdi","year":"1989","unstructured":"Bartholdi, J., Tovey, C.A., Trick, M.A.: Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare 6(2), 157\u2013165 (1989). https:\/\/doi.org\/10.1007\/BF00303169","journal-title":"Soc. Choice Welfare"},{"key":"12_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/J.DISOPT.2022.100743","volume":"46","author":"H Chen","year":"2022","unstructured":"Chen, H., Chen, L., Zhang, G.: Block-structured integer programming: can we parameterize without the largest coefficient? Discret. Optim. 46, 100743 (2022). https:\/\/doi.org\/10.1016\/J.DISOPT.2022.100743","journal-title":"Discret. Optim."},{"issue":"1","key":"12_CR4","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/S10107-023-02046-Z","volume":"208","author":"H Chen","year":"2024","unstructured":"Chen, H., Chen, L., Zhang, G.: FPT algorithms for a special block-structured integer program with applications in scheduling. Math. Program. 208(1), 463\u2013496 (2024). https:\/\/doi.org\/10.1007\/S10107-023-02046-Z","journal-title":"Math. Program."},{"key":"12_CR5","doi-asserted-by":"publisher","unstructured":"Chen, L., Kouteck\u00fd, M., Xu, L., Shi, W.: New bounds on augmenting steps of block-structured integer programs. In: Proceedings of the 28th Annual European Symposium on Algorithms, ESA, pp. 33:1\u201333:19 (2020). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2020.33","DOI":"10.4230\/LIPICS.ESA.2020.33"},{"key":"12_CR6","doi-asserted-by":"publisher","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: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1666\u20131681 (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.101","DOI":"10.1137\/1.9781611976465.101"},{"key":"12_CR7","doi-asserted-by":"publisher","unstructured":"Cslovjecsek, J., Eisenbrand, F., Pilipczuk, M., Venzin, M., Weismantel, R.: Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity. In: Proceedings of the 29th Annual European Symposium on Algorithms, ESA, vol.\u00a0204, pp. 33:1\u201333:14 (2021). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2021.33","DOI":"10.4230\/LIPICS.ESA.2021.33"},{"key":"12_CR8","doi-asserted-by":"publisher","unstructured":"Cslovjecsek, J., Kouteck\u00fd, M., Lassota, A., Pilipczuk, M., Polak, A.: Parameterized algorithms for block-structured integer programs with large entries. TheoretiCS 4 (2025). https:\/\/doi.org\/10.46298\/THEORETICS.25.15. previously appeared in SODA 2024","DOI":"10.46298\/THEORETICS.25.15"},{"key":"12_CR9","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103561","volume":"300","author":"P Dvo\u0159\u00e1k","year":"2021","unstructured":"Dvo\u0159\u00e1k, P., Eiben, E., Ganian, R., Knop, D., Ordyniak, S.: The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints. Artif. Intell. 300, 103561 (2021). https:\/\/doi.org\/10.1016\/j.artint.2021.103561","journal-title":"Artif. Intell."},{"key":"12_CR10","doi-asserted-by":"publisher","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, vol.\u00a010. Springer (1987). https:\/\/doi.org\/10.1007\/978-3-642-61568-9","DOI":"10.1007\/978-3-642-61568-9"},{"issue":"2","key":"12_CR11","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15(2), 341\u2013363 (1986). https:\/\/doi.org\/10.1137\/0215024","journal-title":"SIAM J. Comput."},{"issue":"2","key":"12_CR12","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1137\/0222031","volume":"22","author":"H Edelsbrunner","year":"1993","unstructured":"Edelsbrunner, H., Seidel, R., Sharir, M.: On the zone theorem for hyperplane arrangements. SIAM J. Comput. 22(2), 418\u2013429 (1993). https:\/\/doi.org\/10.1137\/0222031","journal-title":"SIAM J. Comput."},{"key":"12_CR13","doi-asserted-by":"publisher","unstructured":"Eisenbrand, F., Hunkenschr\u00f6der, C., Klein, K.: Faster algorithms for integer programs with block structure. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 49:1\u201349:13 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.49","DOI":"10.4230\/LIPIcs.ICALP.2018.49"},{"key":"12_CR14","doi-asserted-by":"publisher","unstructured":"Eisenbrand, F., Rothvoss, T.: A parameterized linear formulation of the integer hull. In: Proceedings of the 2026 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 4560\u20134571 (2026). https:\/\/doi.org\/10.1137\/1.9781611978971.164","DOI":"10.1137\/1.9781611978971.164"},{"issue":"3","key":"12_CR15","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s10559-023-00573-3","volume":"59","author":"T Ermolieva","year":"2023","unstructured":"Ermolieva, T., et al.: Connections between robust statistical estimation, robust decision-making with two-stage stochastic optimization, and robust machine learning problems. Cybern. Syst. Anal. 59(3), 385\u2013397 (2023). https:\/\/doi.org\/10.1007\/s10559-023-00573-3","journal-title":"Cybern. Syst. Anal."},{"key":"12_CR16","doi-asserted-by":"publisher","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Proceedings of the 19th International Symposium on Algorithms and Computation, ISAAC, pp. 294\u2013305 (2008). https:\/\/doi.org\/10.1007\/978-3-540-92182-0_28","DOI":"10.1007\/978-3-540-92182-0_28"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.dam.2017.02.010","volume":"248","author":"J Fiala","year":"2018","unstructured":"Fiala, J., Gavenciak, T., Knop, D., Kouteck\u00fd, M., Kratochv\u00edl, J.: Parameterized complexity of distance labeling and uniform channel assignment problems. Discret. Appl. Math. 248, 46\u201355 (2018). https:\/\/doi.org\/10.1016\/j.dam.2017.02.010","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"12_CR18","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). https:\/\/doi.org\/10.1007\/BF02579200","journal-title":"Combinatorica"},{"key":"12_CR19","doi-asserted-by":"publisher","unstructured":"Gaven\u010diak, T., Kouteck\u00fd, M., Knop, D.: Integer programming in parameterized complexity: five miniatures. Discrete Optimiz. 44(Part 1), 100596 (2022). https:\/\/doi.org\/10.1016\/j.disopt.2020.100596","DOI":"10.1016\/j.disopt.2020.100596"},{"key":"12_CR20","doi-asserted-by":"publisher","unstructured":"Gr\u00fcnbaum, B.: Convex polytopes, Graduate Texts in Mathematics, vol.\u00a0221. Springer, second edn. (2003). https:\/\/doi.org\/10.1007\/978-1-4613-0019-9","DOI":"10.1007\/978-1-4613-0019-9"},{"key":"12_CR21","doi-asserted-by":"publisher","unstructured":"Hemmecke, R., K\u00f6ppe, M., Weismantel, R.: A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs. In: Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization, IPCO, pp. 219\u2013229 (2010). https:\/\/doi.org\/10.1007\/978-3-642-13036-6_17","DOI":"10.1007\/978-3-642-13036-6_17"},{"key":"12_CR22","doi-asserted-by":"publisher","unstructured":"Hemmecke, R., K\u00f6ppe, M., Weismantel, R.: Graver basis and proximity techniques for block-structured separable convex integer minimization problems. Math. Program. ,pp. 1\u201318 (2013). https:\/\/doi.org\/10.1007\/s10107-013-0638-z","DOI":"10.1007\/s10107-013-0638-z"},{"key":"12_CR23","doi-asserted-by":"publisher","unstructured":"Jansen, K., Klein, K., Maack, M., Rau, M.: Empowering the configuration-IP: new PTAS results for scheduling with setup times. Math. Program. 195(1), 367\u2013401 (2022). https:\/\/doi.org\/10.1007\/S10107-021-01694-3","DOI":"10.1007\/S10107-021-01694-3"},{"issue":"3","key":"12_CR24","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). https:\/\/doi.org\/10.1287\/MOOR.12.3.415","journal-title":"Math. Oper. Res."},{"issue":"1","key":"12_CR25","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). https:\/\/doi.org\/10.1007\/S10107-021-01698-Z","journal-title":"Math. Program."},{"issue":"5","key":"12_CR26","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). https:\/\/doi.org\/10.1007\/S10951-017-0550-0","journal-title":"J. Sched."},{"key":"12_CR27","doi-asserted-by":"publisher","unstructured":"Knop, D., Kouteck\u00fd, M., Mnich, M.: Voting and bribing in single-exponential time. ACM Trans. Econom. Comput. 8(3), 12:1\u201312:28 (2020). https:\/\/doi.org\/10.1145\/3396855","DOI":"10.1145\/3396855"},{"key":"12_CR28","doi-asserted-by":"publisher","unstructured":"Kouteck\u00fd, M., Levin, A., Onn, S.: A parameterized strongly polynomial algorithm for block structured integer programs. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 85:1\u201385:14 (2018). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2018.85","DOI":"10.4230\/LIPICS.ICALP.2018.85"},{"key":"12_CR29","doi-asserted-by":"publisher","unstructured":"Lassota, A., Ligthart, K.: Solving 4-block integer linear programs faster using affine decompositions of the right-hand sides (2026). https:\/\/doi.org\/10.48550\/arXiv.2601.23083","DOI":"10.48550\/arXiv.2601.23083"},{"issue":"1","key":"12_CR30","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/S10107-023-01971-3","volume":"204","author":"T Oertel","year":"2024","unstructured":"Oertel, T., Paat, J., Weismantel, R.: A colorful Steinitz lemma with application to block-structured integer programs. Math. Program. 204(1), 677\u2013702 (2024). https:\/\/doi.org\/10.1007\/S10107-023-01971-3","journal-title":"Math. Program."},{"key":"12_CR31","doi-asserted-by":"publisher","unstructured":"Pottier, L.: Minimal solutions of linear diophantine systems : bounds and algorithms. In: Proceedings of the International Conference on Rewriting Techniques and Applications, RTA, pp. 162\u2013173 (1991). https:\/\/doi.org\/10.1007\/3-540-53904-_94","DOI":"10.1007\/3-540-53904-_94"},{"issue":"2","key":"12_CR32","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/OPRE.34.2.250","volume":"34","author":"\u00c9 Tardos","year":"1986","unstructured":"Tardos, \u00c9.: A strongly polynomial algorithm to solve combinatorial linear programs. Opererations Rese. 34(2), 250\u2013256 (1986). https:\/\/doi.org\/10.1287\/OPRE.34.2.250","journal-title":"Opererations Rese."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28691-8_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:33:46Z","timestamp":1781303626000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Padua","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}