Approximation Algorithms for Union and Intersection Covering Problems

Details Approximation Algorithms for Union and Intersection Covering Problems Approximation Algorithms for Union and Intersection Covering Problems

2011-02-24

arxiv.org/abs/1102.5105v1

Computer Science

Data Structures and Algorithms

Scientific paper

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 and edges represent requests and items, respectively. 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 a 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 connecting a subset of users to both electricity and water. We present a number of hardness and approximation results for union and intersection versions of several standard optimization problems: MST, Steiner tree, set cover, facility location, TSP, and their partial covering variants.

Affiliated with

Also associated with

No associations

Rating

Approximation Algorithms for Union and Intersection Covering Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation Algorithms for Union and Intersection Covering Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for Union and Intersection Covering Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-708984