Document Open Access Logo

Lift & Project Systems Performing on the Partial Vertex Cover Polytope

Authors Konstantinos Georgiou, Edward Lee

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.199.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Konstantinos Georgiou
Edward Lee

Cite As Get BibTex

Konstantinos Georgiou and Edward Lee. Lift & Project Systems Performing on the Partial Vertex Cover Polytope. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 199-211, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.199

Abstract

We study integrality gap (IG) lower bounds on strong LP and SDP relaxations derived by the Sherali-Adams (SA), Lovász-Schrijver-SDP (LS_+), and Sherali-Adams-SDP (SA_+) lift-and-project (L&P) systems for the t-Partial-Vertex-Cover (t-PVC) problem, a variation of the classic Vertex-Cover problem in which only t edges need to be covered. t-PVC admits a 2-approximation using various algorithmic techniques, all relying on a natural LP relaxation. Starting from this LP relaxation, our main results assert that for every epsilon>0, level-Theta(n) LPs or SDPs derived by all known L&P systems that have been used for positive algorithmic results (but the Lasserre hierarchy) have IGs at least (1-epsilon)n/t, where n is the number of vertices of the input graph. Our lower bounds are nearly tight, in that level-n relaxations, even of the weakest systems, have integrality gap 1. 

As lift-and-project systems have given the best algorithms known for numerous combinatorial optimization problems, our results show that restricted yet powerful models of computation derived by many L&P systems fail to witness c-approximate solutions to t-PVC for any constant c, and for t=O(n). This is one of the very few known examples of an intractable combinatorial optimization problem for which LP-based algorithms induce a constant approximation ratio, still lift-and-project LP and SDP tightenings of the same LP have unbounded IGs.

As further motivation for our results, we show that the SDP that has given the best algorithm known for t-PVC has integrality gap n/t on instances that can be solved by the level-1 LP relaxation derived by the LS system. This constitutes another rare phenomenon where (even in specific instances) a static LP outperforms an SDP that has been used for the best approximation guarantee for the problem at hand. 

Finally, we believe our results are of independent interest as they are among the very few known integrality gap lower bounds for LP and SDP 0-1 relaxations in which not all variables possess the same semantics in the underlying combinatorial optimization problem. Most importantly, one of our main contributions is that we make explicit of a new and simple methodology of constructing solutions to LP relaxations that almost trivially satisfy constraints derived by all SDP L&P systems known to be useful for algorithmic positive results (except the La system). The latter sheds some light as to why La tightenings seem strictly stronger than LS_+ or SA_+ tightenings.

Subject Classification

Keywords
  • Partial vertex cover
  • combinatorial optimization
  • linear programming
  • semidefinite programming
  • lift and project systems
  • integrality gaps

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Y. Au and L. Tunçel. A comprehensive analysis of polyhedral lift-and-project methods. CoRR, abs/1312.5972, 2013. Google Scholar
  2. S. Benabbas, S. O. Chan, K. Georgiou, and A. Magen. Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy. In FSTTCS, volume 13 of LIPIcs, pages 41-54, 2011. Google Scholar
  3. S. K. Bera, S. Gupta, A. Kumar, and S. Roy. Approximation algorithms for the partition vertex cover problem. In WALCOM, volume 7748 of LNCS, pages 137-145. Springer, 2013. Google Scholar
  4. N. H. Bshouty and L. Burroughs. Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In STACS, volume 1373 of LNCS, pages 298-308. Springer, 1998. Google Scholar
  5. B. Caskurlu and K. Subramani. On partial vertex cover on bipartite graphs and trees. CoRR, abs/1304.5934, 2013. Google Scholar
  6. M. Charikar, K. Makarychev, and Y. Makarychev. Integrality gaps for Sherali-Adams relaxations. In STOC, pages 283-292, New York, NY, USA, 2009. ACM Press. Google Scholar
  7. K. K. H. Cheung. Computation of the lasserre ranks of some polytopes. Math. Oper. Res, 32(1), 2007. Google Scholar
  8. E. Chlamtáč and M. Tulsiani. Convex relaxations and integrality gaps. In Miguel F. Anjos and Jean B. Lasserre, editors, Handbook on Semidefinite, Conic and Polynomial Optimization, volume 166 of International Series in Operations Research & Management Science, pages 139-169. Springer US, 2012. Google Scholar
  9. W. Cook and S. Dash. On the matrix-cut rank of polyhedra. Mathematics of Operations Research, 26(1):19-30, 2001. Google Scholar
  10. Irit Dinur and Shmuel Safra. On the hardness of approximating minimum vertex-cover. Annals of Mathematics, 162(1):439-486, 2005. Google Scholar
  11. R. Gandhi, S. Khuller, and A. Srinivasan. Approximation algorithms for partial covering problems. J. Algorithms, 53(1):55-84, 2004. Google Scholar
  12. K. Georgiou and E. Lee. Lift and project systems performing on the partial-vertex-cover polytope. CoRR, abs/1409.6365v1, 2014. Google Scholar
  13. K. Georgiou and A. Magen. Expansion Fools the Sherali-Adams System: Compromising Local and Global Arguments. Technical Report CSRG-587, University of Toronto, November 2008. Google Scholar
  14. K. Georgiou, A. Magen, T. Pitassi, and I. Tourlakis. Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy. SIAM J. Comput, 39(8):3553-3570, 2010. Google Scholar
  15. E. Halperin and A. Srinivasan. Improved approximation algorithms for the partial vertex cover problem. In APPROX, volume 2462, pages 161-174. Springer, 2002. Google Scholar
  16. D. S. Hochbaum. The t-vertex cover problem: Extending the half integrality framework with budget constraints. In APPROX, volume 1444 of LNCS, pages 111-122. Springer Berlin Heidelberg, 1998. Google Scholar
  17. C. Kenyon-Mathieu and W. F. de la Vega. Linear programming relaxations of maxcut. In SODA, pages 53-61. ACM Press, 2007. Google Scholar
  18. S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2-ε. J. Comput. Syst. Sci., 74(3):335-349, 2008. Google Scholar
  19. S. G. Kolliopoulos and Y. Moysoglou. Sherali-Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained Facility Location. In APPROX, LNCS, page to appear, 2014. Google Scholar
  20. J. Könemann, O. Parekh, and D. Segev. A unified approach to approximating partial covering problems. Algorithmica, 59:489-509, 2011. Google Scholar
  21. J. B. Lasserre. An explicit exact SDP relaxation for nonlinear 0-1 programs. In IPCO, volume 2081 of LNCS, pages 293-303. Springer, Berlin, 2001. Google Scholar
  22. M. Laurent. A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res., 28(3):470-496, 2003. Google Scholar
  23. L. Lovász and A. Schrijver. Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization, 1(2):166-190, May 1991. Google Scholar
  24. M. Mastrolilli. The lasserre hierarchy in almost diagonal form. CoRR, abs/1312.6493, 2013. Google Scholar
  25. J. Mestre. A primal-dual approximation algorithm for partial vertex cover: Making educated guesses. Algorithmica, 55(1):227-239, 2009. Google Scholar
  26. G. Schoenebeck. Linear level lasserre lower bounds for certain k-CSPs. In FOCS, pages 593-602. IEEE Computer Society, 2008. Google Scholar
  27. G. Schoenebeck, L. Trevisan, and M. Tulsiani. Tight integrality gaps for Lovász-Schrijver LP relaxations of vertex cover and max cut. In STOC, pages 302-310. ACM Press, 2007. Google Scholar
  28. H. D. Sherali and W. P. Adams. A hierarchy of relaxations between the continuous and convex hull representations for 0-1 programming problems. SIAM J. Discrete Math., 3(3):411-430, 1990. Google Scholar
  29. A. Srinivasan. Distributions on level-sets with applications to approximation algorithms. In FOCS, pages 588-599, 2001. Google Scholar
  30. Iannis Tourlakis. New lower bounds for approximation algorithms in the Lóvasz-Schrijver hierarchy. PhD thesis, Department of Computer Science, June 2006. Google Scholar
  31. J. Tu, J. Du, and F. Yang. An iterative rounding 2-approximation algorithm for the k-partial vertex cover problem. Acta Mathematicae Applicatae Sinica, English Series, 30(2):271-278, 2014. Google Scholar
  32. M. Tulsiani. CSP gaps and reductions in the Lasserre hierarchy. In STOC, pages 303-312, New York, NY, USA, 2009. ACM Press. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact