Cygan, Marek ;
Grandoni, Fabrizio ;
Leonardi, Stefano ;
Mucha, Marcin ;
Pilipczuk, Marcin ;
Sankowski, Piotr
Approximation Algorithms for Union and Intersection Covering Problems
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 kMST problem we want to find the cheapest tree spanning at least k nodes of an edgeweighted graph. Here, nodes represent requests whereas edges correspond to items.
In this paper, we initiate the study of a new family of multilayer 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 multilayer problem, a request is satisfied if it is satisfied in at least one layer;
 in an intersection multilayer problem, a request is satisfied if it is satisfied in all layers.
To see some natural applications, consider both generalizations of kMST. Union kMST 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 kMST 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 = {2840},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897347},
ISSN = {18688969},
year = {2011},
volume = {13},
editor = {Supratik Chakraborty and Amit Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3321},
URN = {urn:nbn:de:0030drops33213},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.28},
annote = {Keywords: Approximation algorithms, Partial covering problems}
}
Keywords: 

Approximation algorithms, Partial covering problems 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Issue date: 

2011 
Date of publication: 

2011 