Lagrangian Relaxation and Partial Cover (Extended Abstract)

JuliáN Mestre
Lagrangian relaxation has been used extensively in the design of approximation algorithms. This paper studies its strengths and limitations when applied to Partial Cover. We show that for Partial Cover in general no algorithm that uses Lagrangian relaxation and a Lagrangian Multiplier Preserving (LMP) $alpha$-approximation as a black box can yield an approximation factor better than~$frac{4}{3} alpha$. This matches the upper bound given by K"onemann et al. (ESA 2006, pages 468--479). Faced with this limitation...