Welcome to Fnd2012 Open Problems, where you can ask questions and receive answers from other members of the community.

Can one improve approximation algorithms for union and intersection covering problems?

0 votes

In this paper we have introduced union and intersection covering problems. In such problems we are given h layers - graphs with the same set of vertices. In each layer we need to solve some graph problem to cover vertices, e.g., connect vertices to the root by using a Steiner tree. In intersection problems we are asked to chose k-vertices of the graphs and cover them in all the layers, on the other hand in union problems, we are asked to cover all vertices but each vertex should be covered in at least one layer.

There are two interesting open problems here:

- We were able to give O(h) approximation algorithm for the union problem of, e.g., Steiner trees. Can on get a constant approximation that would be independent of h (for reasonably small h)?

- Can one close the gap between upper and lower bounds for intersection problems? In particular, our hardness results do not depend on h, while the approximation ratios deteriorate rather rapidly for increasing h.

asked Jul 31, 2012 by sank (180 points)