Computing the Integer Programming Gap

Simple item page
dc.creatorHosten, Serkan
dc.creatorSturmfels, Bernd
dc.date2003-01-23
dc.date.accessioned2026-07-07T04:54:38Z
dc.date.available2026-07-07T04:54:38Z
dc.descriptionWe determine the maximal gap between the optimal values of an integer program and its linear programming relaxation, where the matrix and cost function are fixed but the right hand side is unspecified. Our formula involves irreducible decomposition of monomial ideals. The gap can be computed in polynomial time when the dimension is fixed.
dc.description17 Pages
dc.identifierhttps://arxiv.org/abs/math/0301266
dc.identifierhttp://arxiv.org/abs/math/0301266
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/66335
dc.subjectOptimization and Control
dc.subjectCommutative Algebra
dc.subjectCombinatorics
dc.subject90C10 (Primary), 13P10, 62H17 (Secondary)
dc.titleComputing the Integer Programming Gap
dc.typetext

Files

Collections

arXiv