Computing the Integer Programming Gap

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We 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.
17 Pages

Keywords

Optimization and Control, Commutative Algebra, Combinatorics, 90C10 (Primary), 13P10, 62H17 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/66335

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0301266
 http://arxiv.org/abs/math/0301266

Collections

arXiv