Lagrangian Relaxation and Partial Cover (Extended Abstract)

Abstract

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 we study a specific, yet broad class of
  covering problems: Partial Totally Balanced Cover.  By carefully
  analyzing the inner workings of the LMP algorithm we are able to
  give an almost tight characterization of the integrality gap of the
  standard linear relaxation of the problem.  As a consequence we
  obtain improved approximations for the Partial version of Multicut
  and Path Hitting on Trees, Rectangle Stabbing, and Set Cover with
  $
ho$-Blocks.