English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

We study integrality gap (IG) lower bounds on strong LP and SDP relaxationsderived by the Sherali-Adams (SA), Lovasz-Schrijver-SDP (LS+), andSherali-Adams-SDP (SA+) lift-and-project (L&P) systems for thet-Partial-Vertex-Cover (t-PVC) problem, a variation of the classic Vertex-Coverproblem in which only t edges need to be covered. t-PVC admits a2-approximation using various algorithmic techniques, all relying on a naturalLP relaxation. Starting from this LP relaxation, our main results assert thatfor every epsilon > 0, level-Theta(n) LPs or SDPs derived by all known L&Psystems that have been used for positive algorithmic results (but the Lasserrehierarchy) have IGs at least (1-epsilon)n/t, where n is the number of verticesof the input graph. Our lower bounds are nearly tight.  Our results show that restricted yet powerful models of computation derivedby many L&P systems fail to witness c-approximate solutions to t-PVC for anyconstant c, and for t = O(n). This is one of the very few known examples of anintractable combinatorial optimization problem for which LP-based algorithmsinduce a constant approximation ratio, still lift-and-project LP and SDPtightenings of the same LP have unbounded IGs.  We also show that the SDP that has given the best algorithm known for t-PVChas integrality gap n/t on instances that can be solved by the level-1 LPrelaxation derived by the LS system. This constitutes another rare phenomenonwhere (even in specific instances) a static LP outperforms an SDP that has beenused for the best approximation guarantee for the problem at hand. Finally, oneof our main contributions is that we make explicit of a new and simplemethodology of constructing solutions to LP relaxations that almost triviallysatisfy constraints derived by all SDP L&P systems known to be useful foralgorithmic positive results (except the La system).

Lift & Project Systems Performing on the Partial-Vertex-Cover Polytope