2026-08-10T09:35:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3321 2024-03-06T10:34:03Z ddc:004 open_access

Approximation Algorithms for Union and Intersection Covering Problems Cygan, Marek Grandoni, Fabrizio Leonardi, Stefano Mucha, Marcin Pilipczuk, Marcin Sankowski, Piotr Approximation algorithms Partial covering problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marek Cygan and Fabrizio Grandoni and Stefano Leonardi and Marcin Mucha and Marcin Pilipczuk and Piotr Sankowski 2011 Is Part Of LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2011.28 urn:nbn:de:0030-drops-33213 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.28 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode