License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.28
URN: urn:nbn:de:0030-drops-33213
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3321/
Go to the corresponding LIPIcs Volume Portal

Cygan, Marek ; Grandoni, Fabrizio ; Leonardi, Stefano ; Mucha, Marcin ; Pilipczuk, Marcin ; Sankowski, Piotr

Approximation Algorithms for Union and Intersection Covering Problems

pdf-format:
3.pdf (0.5 MB)

Abstract

In a classical covering problem, we are given a set of requests that we need to satisfy (fully or partially), by buying a subset of items at minimum cost. For example, in the k-MST problem we want to find the cheapest tree spanning at least k nodes of an edge-weighted graph. Here, nodes represent requests whereas edges correspond to items.

In this paper, we initiate the study of a new family of multi-layer covering problems. Each such problem consists of a collection of h distinct instances of a standard covering problem (layers), with the constraint that all layers share the same set of requests. We identify two main subfamilies of these problems:
- in an union multi-layer problem, a request is satisfied if it is satisfied in at least one layer;
- in an intersection multi-layer problem, a request is satisfied if it is satisfied in all layers.
To see some natural applications, consider both generalizations of k-MST. Union k-MST can model a problem where we are asked to connect a set of users to at least one of two communication networks, e.g., a wireless and a wired network. On the other hand, Intersection k-MST can formalize the problem of providing both electricity and water to at least k users.

BibTeX - Entry

@InProceedings{cygan_et_al:LIPIcs:2011:3321,
  author =	{Marek Cygan and Fabrizio Grandoni and Stefano Leonardi and Marcin Mucha and Marcin Pilipczuk and Piotr Sankowski},
  title =	{{Approximation Algorithms for Union and Intersection Covering Problems }},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{28--40},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3321},
  URN =		{urn:nbn:de:0030-drops-33213},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.28},
  annote =	{Keywords: Approximation algorithms, Partial covering problems}
}

Keywords: Approximation algorithms, Partial covering problems
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011

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