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. © M. Cygan, F. Grandoni, S. Leonardi, M. Mucha, M. Pilipczuk, P. Sankowski.
Approximation algorithms for union and intersection covering problems / Marek, Cygan; Fabrizio, Grandoni; Leonardi, Stefano; Marcin, Mucha; Marcin, Pilipczuk; Piotr, Sankowski. - STAMPA. - 13:(2011), pp. 28-40. (Intervento presentato al convegno 31st International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011 tenutosi a Mumbai; India nel 12 December 2011 through 14 December 2011) [10.4230/lipics.fsttcs.2011.28].
Approximation algorithms for union and intersection covering problems
LEONARDI, Stefano;
2011
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. © M. Cygan, F. Grandoni, S. Leonardi, M. Mucha, M. Pilipczuk, P. Sankowski.File | Dimensione | Formato | |
---|---|---|---|
VE_2011_11573-559141.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
510.94 kB
Formato
Adobe PDF
|
510.94 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.