Abstract
Consider an integer program max (c t x : Ax = b, x ≥ 0, x ∈ Z n) where A ∈ Z m×n, b ∈ Z m, and c ∈ Z n. We show that the integer program can be solved in pseudo-polynomial time when A is non-negative and the column-matroid of A has constant branch-width.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Courcelle, B.: Graph rewriting: An algebraic and logical approach. In: van Leeuwnen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, North-Holland, Amsterdam (1990)
Cunningham, W.H.: Improved bounds for matroid partition and intersection algorithms. SIAM J. Comput. 15, 948–957 (1986)
Garey, M.R., Johnson, D.S.: Computers and Intractability. A guide to the theory of NP-completeness. A series of books in the mathematical sciences. H. Freeman and Co., San Francisco (1979)
Hliněný, P.: Branch-width, parse trees and monadic second-order logic for matroids. Manuscript (2002)
Lueker, G.S.: Two NP-complete problems in non-negative integer programming. Report No. 178, Department of Computer Science, Princeton University, Princeton, N.J. (1975)
Oum, S., Seymour, P.D.: Approximating clique-width and branch-width. J. Combin. Theory, Ser. B 96, 514–528 (2006)
Oum, S., Seymour, P.D.: Testing branch-width. To appear in J. Combin. Theory, Ser. B
Oxley, J.G.: Matroid Theory. Oxford University Press, New York (1992)
Papadimitriou, C.H.: On the complexity of integer programming. J. Assoc. Comput. Mach. 28, 765–768 (1981)
Robertson, N., Seymour, P.D.: Graph Minors. X. Obstructions to tree-decomposition. J. Combin. Theory, Ser. B 52, 153–190 (1991)
Robertson, N., Seymour, P.D.: Graph Minors. XVI. Excluding a non-planar graph. J. Combin. Theory, Ser. B 89, 43–76 (2003)
Seymour, P.D.: Decomposition of regular matroids. J. Combin. Theory, Ser. B 28, 305–359 (1980)
Tutte, W.T.: A homotopy theorem for matroids, I, II. Trans. Amer. Math. Soc. 88, 144–174 (1958)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Cunningham, W.H., Geelen, J. (2007). On Integer Programming and the Branch-Width of the Constraint Matrix. In: Fischetti, M., Williamson, D.P. (eds) Integer Programming and Combinatorial Optimization. IPCO 2007. Lecture Notes in Computer Science, vol 4513. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72792-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-540-72792-7_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72791-0
Online ISBN: 978-3-540-72792-7
eBook Packages: Computer ScienceComputer Science (R0)