N-Fold Integer Programming

Simple item page
dc.creatorDe Loera, Jesús A.
dc.creatorHemmecke, Raymond
dc.creatorOnn, Shmuel
dc.creatorWeismantel, Robert
dc.date2006-05-09
dc.date.accessioned2026-07-07T09:52:26Z
dc.date.available2026-07-07T09:52:26Z
dc.descriptionIn this article we study a broad class of integer programming problems in variable dimension. We show that these so-termed {\em n-fold integer programming problems} are polynomial time solvable. Our proof involves two heavy ingredients discovered recently: the equivalence of linear optimization and so-called directed augmentation, and the stabilization of certain Graver bases. We discuss several applications of our algorithm to multiway transportation problems and to packing problems. One important consequence of our results is a polynomial time algorithm for the $d$-dimensional integer transportation problem for long multiway tables. Another interesting application is a new algorithm for the classical cutting stock problem.
dc.identifierhttps://arxiv.org/abs/math/0605242
dc.identifierhttp://arxiv.org/abs/math/0605242
dc.identifierDiscrete Optimization, 5:231--241, 2008
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/165592
dc.subjectOptimization and Control
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.subjectCombinatorics
dc.subject05A; 15A; 51M; 52A; 52B; 52C; 68Q; 68R; 68U; 90B; 90C
dc.titleN-Fold Integer Programming
dc.typetext

Files

Collections

arXiv