C. Thach Nguyen

  1. Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack.

    Authors: Claire Mathieu, Anna R. Karlin, C. Thach Nguyen
    Subjects: Computational Complexity
    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 - {\epsilon} persists up to a linear number of rounds of
    Sherali-Adams, despite the fact that Knapsack admits a fully polynomial time
    approximation scheme [27,33]. 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).

Syndicate content