| Title | Computing the integer programming gap. |
| Author(s) | Serkan Hosten, Bernd Sturmfels |
| Type | Article in Journal |
| Abstract | 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. |
| ISSN | 0209-9683; 1439-6912/e |
| URL |
http://link.springer.com/article/10.1007%2Fs00493-007-2057-3 |
| Language | English |
| Journal | Combinatorica |
| Volume | 27 |
| Number | 3 |
| Pages | 367--382 |
| Publisher | Springer, Berlin/Heidelberg; J |
| Year | 2007 |
| Edition | 0 |
| Translation |
No |
| Refereed |
No |
