The Complexity of Recognizing Facets for the Knapsack Polytope

References

• [1] Balas E (1975) Facets of the knapsack polytope. Math. Programming 8(1):146–164.Crossref, Google Scholar
• [2] Balas E, Zemel E (1978) Facets of the knapsack polytope from minimal covers. SIAM J. Appl. Math. 34(1):119–148.Crossref, Google Scholar
• [3] Boyd EA (1994) Fenchel cutting planes for integer programs. Oper. Res. 42(1):53–64.Link, Google Scholar
• [4] Bulut A, Ralphs TK (2021) On the complexity of inverse mixed integer linear optimization. SIAM J. Optim. 31(4):3014–3043.Crossref, Google Scholar
• [5] Cai JY, Meyer GE (1987) Graph minimal uncolorability is DP-complete. SIAM J. Comput. 16(2):259–277.Crossref, Google Scholar
• [6] Chen WK, Dai YH (2021) On the complexity of sequentially lifting cover inequalities for the knapsack polytope. Sci. China Math. 64(1):211–220.Crossref, Google Scholar
• [7] Chopra S (1989) On the spanning tree polyhedron. Oper. Res. Lett. 8(1):25–29.Crossref, Google Scholar
• [8] Crowder H, Johnson EL, Padberg M (1983) Solving large-scale zero-one linear programming problems. Oper. Res. 31(5):803–834.Link, Google Scholar
• [9] Del Pia A, Linderoth J, Zhu H (2023) Multi-cover inequalities for totally-ordered multiple knapsack sets: Theory and computation. Math. Programming 197(2):847–875.Crossref, Google Scholar
• [10] Goemans MX, Rothvoβ T (2020) Polynomiality for bin packing with a constant number of item types. J. ACM 67(6):1–21.Crossref, Google Scholar
• [11] Grötschel M, Padberg MW (1979) On the symmetric travelling salesman problem I: Inequalities. Math. Programming 16:265–280.Crossref, Google Scholar
• [12] Gu Z (1995) Lifted cover inequalities for 0-1 and mixed 0-1 integer programs. PhD thesis, Georgia Institute of Technology, Atlanta.Google Scholar
• [13] Hammer PL, Johnson EL, Peled UN (1975) Facet of regular 0–1 polytopes. Math. Programming 8(1):179–206.Crossref, Google Scholar
• [14] Hartvigsen D, Zemel E (1992) The complexity of lifted inequalities for the knapsack problem. Discrete Appl. Math. 39(2):113–123.Crossref, Google Scholar
• [15] Jansen K, Klein KM (2020) About the structure of the integer cone and its application to bin packing. Math. Oper. Res. 45(4):1498–1511.Link, Google Scholar
• [16] Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, Bohlinger JD, eds. Complexity of Computer Computations, The IBM Research Symposia Series (Springer, Boston), 85–103.Crossref, Google Scholar
• [17] Karp RM, Papadimitriou CH (1982) On linear characterizations of combinatorial optimization problems. SIAM J. Comput. 11(4):620–632.Crossref, Google Scholar
• [18] Marchand H, Martin A, Weismantel R, Wolsey L (2002) Cutting planes in integer and mixed integer programming. Discrete Appl. Math. 123(1–3):397–446.Crossref, Google Scholar
• [19] Papadimitriou CH, Wolfe D (1985) The complexity of facets resolved. Technical report, Cornell University, Ithaca, NY.Google Scholar
• [20] Papadimitriou CH, Yannakakis M (1982) The complexity of facets (and some facets of complexity). Proc. 14th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 255–260.Google Scholar
• [21] Rothe J (2003) Exact complexity of exact-four-colorability. Inform. Processing Lett. 87(1):7–12.Crossref, Google Scholar
• [22] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, vol. 24 (Springer, Berlin, Heidelberg).Google Scholar
• [23] Weismantel R (1997) On the 0/1 knapsack polytope. Math. Programming 77(3):49–68.Crossref, Google Scholar
• [24] Wolsey LA (1975) Faces for a linear inequality in 0–1 variables. Math. Programming 8(1):165–178.Crossref, Google Scholar