License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1315
URN: urn:nbn:de:0030-drops-13156
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1315/
Go to the corresponding LIPIcs Volume Portal

Mestre, Julián

Lagrangian Relaxation and Partial Cover (Extended Abstract)

pdf-format:
22011.MestreJulian.Paper.1315.pdf (0.2 MB)

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.


BibTeX - Entry

@InProceedings{mestre:LIPIcs:2008:1315,
  author =	{Juli{\'a}n Mestre},
  title =	{{Lagrangian Relaxation and Partial Cover (Extended Abstract)}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{539--550},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1315},
  URN =		{urn:nbn:de:0030-drops-13156},
  doi =		{10.4230/LIPIcs.STACS.2008.1315},
  annote =	{Keywords: Lagrangian Relaxation, Partial Cover, Primal-Dual Algorithms}
}

Keywords: Lagrangian Relaxation, Partial Cover, Primal-Dual Algorithms
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI