Integer Programs with Nearly Totally Unimodular Matrices: The Cographic Case
Mathematics of Operations Research · 09.06.2026
DOI: 10.1287/moor.2024.0830 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Operations Research, online erschienen am 09.06.2026. Verfasst von Manuel Aprile und 6 weiteren Autor:innen. Die Arbeit nennt 73 Literaturangaben.
Abstract (Originalsprache)
It is a notorious open question whether integer programs (IPs) with an integer coefficient matrix M whose subdeterminants are all bounded by a constant [Formula: see text] in absolute value can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains a submatrix A that is the transpose of a network matrix. Our approach focuses on the case in which A arises from M after removing k rows only and k is a constant. We achieve our result in two main steps, the first related to the theory of IPs and the second related to graph minor theory. First, we derive a strong proximity result for the case in which A is a general totally unimodular matrix: given an optimal solution of the linear programming relaxation, an optimal solution to the IP can be obtained by finding a constant number of augmentations by circuits of [Formula: see text]. Second, for the case in which A is the transpose of a network matrix, we reformulate the problem as a maximum constrained integer potential problem on a graph G. We observe that, if G is two-connected, then it has no rooted [Formula: see text]-minor for [Formula: see text]. We leverage this to obtain a tree-decomposition of G into highly structured graphs for which we can solve the problem locally. This allows us to solve the global problem via dynamic programming. Funding: M. Aprile and S. Fiorini acknowledge funding from Fonds de la Recherche Scientifique (FNRS) through research project BD-DELTA [Grant PDR 20222190, 2021–24]. S. Fiorini was also funded by the King Baudouin Foundation through project BD-DELTA-2 (convention 2023-F2150080-233051, 2023–26). G. Joret and M. Seweryn acknowledge funding from FNRS (PDR “Product structure of planar graphs”). S. Kober and S. Weltge were supported by the Deutsche Forschungsgemeinschaft (German Research Foundation) [Grants 277991500/GRK2201 and 451026932, respectively]. Y. Yuditsky was supported by FNRS as a postdoctoral researcher.
Zitieren
APA
Aprile, M., Fiorini, S., Joret, G., Kober, S., Seweryn, M., Weltge, S., & Yuditsky, Y. (2026). Integer Programs with Nearly Totally Unimodular Matrices: The Cographic Case. Mathematics of Operations Research. https://doi.org/10.1287/moor.2024.0830
Vancouver
Aprile M, Fiorini S, Joret G, Kober S, Seweryn M, Weltge S, et al. Integer Programs with Nearly Totally Unimodular Matrices: The Cographic Case. Mathematics of Operations Research. 2026. doi:10.1287/moor.2024.0830
BibTeX
@article{Aprile2026,
author = {Aprile, Manuel and Fiorini, Samuel and Joret, Gwenaël and Kober, Stefan and Seweryn, Michał and Weltge, Stefan and Yuditsky, Yelena},
title = {Integer Programs with Nearly Totally Unimodular Matrices: The Cographic Case},
journal = {Mathematics of Operations Research},
year = {2026},
doi = {10.1287/moor.2024.0830}
}
EUVIMED