I detta dokument studerar vi integrality gapet i Knapsack linjära programmet i SheraliAdams och Lasserre hierarkier. För det första visar vi att en integrality gap av 2 −  påstått upp till ett linjärt antal rundor av Sherali-Adams, trots det faktum att Knapsack medger en helt polynom tid approximation system [27, 33]. För det andra visar vi att Lasserrehierarkin snabbt minskar klyftan. Särskilt efter t-rundor av Lasserre minskar integratitetsgapet till t/(t − 1). Såvitt vi vet är detta det första positiva resultatet som använder mer än ett litet antal rundor i Lasserre-hierarkin. Vårt bevis använder ett nedbrytningsteorem för Lasserre hierarkin, som kan vara av oberoende intresse.
Karlin, Mathieu och Nguyen visar att 1/ε rundor av Lasserre SDP ger en (1 + ε) approximation till Knapsack problem REF.
Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}