Integrality Gaps of Integer Knapsack Problems

1. Aliev, I.: On the lattice programming gap of the group problems. Oper. Res. Lett. 43, 199–202 (2015)

   Article  MathSciNet  Google Scholar 

2. Aliev, I., Gruber, P.M.: An optimal lower bound for the Frobenius problem. J. Number Theor. 123, 71–79 (2007)

   Article  MathSciNet  MATH  Google Scholar 

3. Bertsimas, D., Weismantel, R.: Optimization Over Integers. Dynamic Ideas, Massachusetts (2005)

   Google Scholar 

4. Blair, C.E., Jeroslow, R.G.: The value function of a mixed integer program: I. Discrete Math. 19, 121–138 (1977)

   Article  MathSciNet  MATH  Google Scholar 

5. Blair, C.E., Jeroslow, R.G.: The value function of an integer program. Math. Program. 23, 237–273 (1982)

   Article  MathSciNet  MATH  Google Scholar 

6. Brauer, A.: On a problem of partitions. Am. J. Math. 64, 299–312 (1942)

   Article  MATH  Google Scholar 

7. Chandrasekaran, R.: Polynomial algorithms for totally dual integral systems and extensions. Studies on graphs and discrete programming (Brussels, 1979). Ann. Discrete Math. 11, 39–51. North-Holland, Amsterdam (1981)

   Google Scholar 

8. Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Graduate Texts in Mathematics, vol. 271. Springer, Heidelberg (2014)

   MATH  Google Scholar 

9. Cook, W., Gerards, A.M.H., Schrijver, A., Tardos, É.: Sensitivity theorems in integer linear programming. Math. Program. 34, 251–264 (1986)

   Article  MathSciNet  MATH  Google Scholar 

10. Dougherty, R., Faber, V.: The degree-diameter problem for several varieties of Cayley graphs I: the abelian case. SIAM J. Discrete Math. 17, 478–519 (2004)

    Article  MathSciNet  MATH  Google Scholar 

11. Eisenbrand, F., Hähnle, N., Pálvölgyi, D., Shmonin, G.: Testing additive integrality gaps. Math. Program. A 141, 257–271 (2013)

    Article  MathSciNet  MATH  Google Scholar 

12. Eisenbrand, F., Shmonin, G.: Parametric integer programming in fixed dimension. Math. Oper. Res. 33, 839–850 (2008)

    Article  MathSciNet  MATH  Google Scholar 

13. Fáry, I.: Sur la densité des réseaux de domaines convexes. Bull. Soc. Math. France 78, 152–161 (1950)

    Article  MathSciNet  MATH  Google Scholar 

14. 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. W.H. Freeman and Co., San Francisco (1979)

    MATH  Google Scholar 

15. Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64, 275–278 (1958)

    Article  MathSciNet  MATH  Google Scholar 

16. Gruber, P.M.: Convex and Discrete Geometry. Springer, Berlin (2007)

    MATH  Google Scholar 

17. Gruber, P.M., Lekkerkerker, C.G.: Geometry of Numbers. North-Holland, Amsterdam (1987)

    MATH  Google Scholar 

18. Hoşten, S., Sturmfels, B.: Computing the integer programming gap. Combinatorica 27(3), 367–382 (2007)

    Article  MathSciNet  MATH  Google Scholar 

19. Kannan, R.: Lattice translates of a polytope and the Frobenius problem. Combinatorica 12, 161–177 (1992)

    Article  MathSciNet  MATH  Google Scholar 

20. Khachiyan, L.G.: Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 1(20), 53–72 (1980)

    Article  MATH  Google Scholar 

21. Marklof, J., Strömbergsson, A.: Diameters of random circulant graphs. Combinatorica 33, 429–466 (2013)

    Article  MathSciNet  MATH  Google Scholar 

22. Ramírez Alfonsín, J.L.: The Diophantine Frobenius Problem. Oxford Lecture Series in Mathematics and its Applications, vol. 30 (2005)

    Google Scholar 

23. Schmidt, W.M.: Asymptotic formulae for point lattices of bounded determinant and subspaces of bounded height. Duke Math. J. 35, 327–339 (1968)

    Article  MathSciNet  MATH  Google Scholar 

24. Schmidt, W.M.: Integer matrices, sublattices of \(\mathbb{Z}^{m}\), and Frobenius numbers. Monatsh. Math. 178, 405–451 (2015)

    Article  MathSciNet  MATH  Google Scholar 

25. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New Jersey (1986)

    MATH  Google Scholar 

26. Strömbergsson, A.: On the limit distribution of Frobenius numbers. Acta Arith. 152, 81–107 (2012)

    Article  MathSciNet  MATH  Google Scholar 

27. Sullivant, S.: Small contingency tables with large gaps. SIAM J. Discrete Math. 18, 787–793 (2005)

    Article  MathSciNet  MATH  Google Scholar 

28. Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)

    MATH  Google Scholar 

Download references