Abstract
In this paper, we study the integrality gap of the Knapsack linear program in the Sherali-Adams and Lasserre hierarchies. First, we show that an integrality gap of 2 – ε persists up to a linear number of rounds of Sherali-Adams, despite the fact that Knapsack admits a fully polynomial time approximation scheme [24, 30]. Second, we show that the Lasserre hierarchy closes the gap quickly. Specifically, after t rounds of Lasserre, the integrality gap decreases to t/(t – 1). This answers the open question in [9]. Also, to the best of our knowledge, this is the first positive result that uses more than a small number of rounds in the Lasserre hierarchy. Our proof uses a decomposition theorem for the Lasserre hierarchy, which may be of independent interest.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alekhnovich, M., Arora, S., Tourlakis, I.: Towards strong non-approximability results in the Lovász-Schrijver hierarchy. In: ACM STOC (2005)
Arora, S., Bollobás, B., Lovász, L., Tourlakis, I.: Proving integrality gaps without knowing the linear program. Theory of Computing 2, 19–51 (2006)
Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2) (2009)
Balas, E.: Facets of the Knapsack Polytope (1998)
Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming 58, 295–324 (1993)
Balas, E., Zemel, E.: Facets of the knapsack polytope from minimal covers. SIAM Journal on Applied Mathematics 34, 119–148 (1978)
Bateni, M.H., Charikar, M., Guruswami, V.: MaxMin allocation via degree lower-bounded arborescences. In: ACM STOC (2009)
Benabbas, S., Magen, A.: Extending SDP integrality gaps to sherali-adams with applications to quadratic programming and maxCutGain. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 299–312. Springer, Heidelberg (2010)
Bienstock, D.: Approximate formulations for 0-1 knapsack sets. Operational Research Letters 36(3), 317–320 (2008)
Bienstock, D., Ozbay, N.: Tree-width and the Sherali-Adams operator. Discrete Optimization 1(1), 13–21 (2004)
Buresh-Oppenheim, J., Galesi, N., Hoory, S., Magen, A., Pitassi, T.: Rank bounds and integrality gaps for cutting plane procedures. In: IEEE FOCS (2003)
Charikar, M.: On semidefinite programming relaxations for graph coloring and vertex cover. In: ACM-SIAM SODA (2002)
Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: ACM STOC (2009)
Cheeger, J., Kleiner, B., Naor, A.: A (logn)Ω (1) integrality gap for the Sparsest Cut SDP. In: IEEE FOCS (2009)
Chlamtac, E.: Approximation algorithms using hierarchies of semidefinite programming relaxations. In: IEEE FOCS (2007)
Chlamtac, E., Singh, G.: Improved approximation guarantees through higher levels of SDP hierarchies. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol. 5171, pp. 49–62. Springer, Heidelberg (2008)
Fernandez de la Vega, W., Kenyon-Mathieu, C.: Linear programming relaxations of MaxCut. In: ACM-SIAM SODA (2007)
Escudero, L.F., Garn, A.: An o(n log n) procedure for identifying facets of the knapsack polytope. Operational Research Letters 31(3), 211–218 (2003)
Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2 − o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy. In: IEEE FOCS (2007)
Georgiou, K., Magen, A., Tourlakis, I.: Vertex cover resists sDPs tightened by local hypermetric inequalities. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. IPCO, pp. 140–153. Springer, Heidelberg (2008)
Georgiou, K., Magen, A., Tulsiani, M.: Optimal sherali-adams gaps from pairwise independence. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol. 5687, pp. 125–139. Springer, Heidelberg (2009)
Hartvigsen, D., Zemel, E.: On the computational complexity of facets and valid inequalities for the knapsack problem. Discrete Applied Math. 39, 113–123 (1992)
Hatami, H., Magen, A., Markakis, E.: Integrality gaps of semidefinite programs for vertex cover and relations to ℓ1 embeddability of negative type metrics. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol. 4627, pp. 164–179. Springer, Heidelberg (2007)
Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM (1975)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack problems. Springer, Heidelberg (2003)
Khot, S., Saket, R.: SDP integrality gaps with local ℓ1-embeddability. In: IEEE FOCS (2009)
Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, p. 293. Springer, Heidelberg (2001)
Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization 11, 796–817 (2001)
Laurent, M.: A comparison of the Sherali-Adams, Lovász-schrijver and Lasserre relaxations for 0-1 programming. Mathematics of Operations Research 28, 470–496 (2003)
Lawler, E.L.: Fast approximation algorithms for knapsack problems. In: IEEE FOCS (1997)
Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization 1, 166–190 (1991)
Pitassi, T., Segerlind, N.: Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures. In: ACM-SIAM SODA (2009)
Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: ACM STOC (2008)
Raghavendra, P., Steurer, D.: Integrality gaps for strong SDP relaxations of unique games. In: IEEE FOCS (2009)
Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-csps. In: IEEE FOCS (2008)
Schoenebeck, G., Trevisan, L., Tulsiani, M.: Tight integrality gaps for Lovász-Schrijver SDP relaxations of vertex cover and max cut. In: ACM STOC, pp. 302–310 (2007)
Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3, 411–430 (1990)
Tourlakis, I.: New lower bounds for vertex cover in the Lovász-Schrijver hierarchy. In: IEEE CCC (2006)
Tulsiani, M.: CSP gaps and reductions in the Lasserre hierarchy. In: ACM STOC (2009)
Weismantel, R.: On the 0/1 knapsack polytope. Mathematical Programming 77, 49–68 (1997)
Wolsey, L.A.: Valid inequalities for 0-1 knapsacks and mips with generalised upper bound constraints. Discrete Applied Mathematics 29(2-3), 251–261 (1990)
Zemel, E.: Easily computable facets of the knapsack problem. Mathematics of Operations Research 14, 760–774 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Karlin, A.R., Mathieu, C., Nguyen, C.T. (2011). Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack. In: Günlük, O., Woeginger, G.J. (eds) Integer Programming and Combinatoral Optimization. IPCO 2011. Lecture Notes in Computer Science, vol 6655. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20807-2_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-20807-2_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20806-5
Online ISBN: 978-3-642-20807-2
eBook Packages: Computer ScienceComputer Science (R0)