About the Structure of the Integer Cone and Its Application to Bin Packing

References

• [1] Barvinok A (2004) Lattice points, polyhedra, and complexity. Goodman JE, O'Rourke J, eds. Handbook of Discrete and Computational Geometry, Discrete Mathematics and Its Applications, 2nd ed. (Chapman and Hall/CRC, Boca Raton, FL), 153–176.Google Scholar
• [2] Caprara A, Dell’Amico M, Díaz-Díaz JC, Iori M, Rizzi R (2014) Friendly bin packing instances without integer round-up property. Math. Programming 150(1):5–17.Crossref, Google Scholar
• [3] Cook W, Hartmann M, Kannan R, McDiarmid C (1992) On integer points in polyhedra. Combinatorica 12(1):27–37.Google Scholar
• [4] Downey RG, Fellows MR (1999) Parameterized Complexity, Monographs in Computer Science (Springer-Verlag, New York).Crossref, Google Scholar
• [5] Eisenbrand F, Rothvoß T (2009) New hardness results for diophantine approximation. Dinur I, Jansen K, Naor J, Rolim J, eds. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Springer, Berlin), 98–110.Crossref, Google Scholar
• [6] Eisenbrand F, Shmonin G (2006) Carathéodory bounds for integer cones. Oper. Res. Lett. 34(5):564–568.Crossref, Google Scholar
• [7] Goemans MX, Rothvoß T (2014) Polynomiality for bin packing with a constant number of item types. SODA '14: Proc. 25th Annual ACM–SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 830–839.Google Scholar
• [8] Graham RL, Knuth DE, Patashnik O (1994) Concrete Mathematics: A Foundation for Computer Science, 2nd ed. (Addison-Wesley Longman Publishing Co., Inc., Boston).Google Scholar
• [9] Hartmann M (1989) Cutting planes and the complexity of the integer hull. Thesis, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY.Google Scholar
• [10] Hayes A, Larman D (1983) The vertices of the knapsack polytope. Discrete Appl. Math. 6(2):135–138.Crossref, Google Scholar
• [11] Henk M, Weismantel R (2002) Diophantine approximations and integer points of cones. Combinatorica 22(3):401–408.Crossref, Google Scholar
• [12] Hoberg R, Rothvoss T (2017) A logarithmic additive integrality gap for bin packing. SODA '17: Proc. 28th Annual ACM–SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2616–2625Google Scholar
• [13] Jansen K, Solis-Oba R (2011) A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths. Math. Oper. Res. 36(4):743–753.Link, Google Scholar
• [14] Kannan R (1987) Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3):415–440.Link, Google Scholar
• [15] Karmarkar N, Karp RM (1982) An efficient approximation scheme for the one-dimensional bin-packing problem. 23rd Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 312–320.Google Scholar
• [16] Lenstra HW Jr (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538–548.Link, Google Scholar
• [17] Onn S (2015) Unimodular integer caratheodory is fixed parameter tractable. Preprint, submitted November 11, https://arxiv.org/abs/1511.03403.Google Scholar
• [18] Rothvoss T (2013) Approximating bin packing within O(log OPT * log log OPT) bins. 2013 IEEE 54th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 20–29Google Scholar
• [19] Scheithauer G, Terno J (1997) Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem. Oper. Res. Lett. 20(2):93–100.Crossref, Google Scholar
• [20] Schrijver A (1986) Theory of Linear and Integer Programming (John Wiley & Sons, Inc., Chichester, UK).Google Scholar
• [21] Stark H (1970) An Introduction to Number Theory, Markham Mathematics Series (Markham Publishing Co., Chicago).Google Scholar