I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union

Question

I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost.

I have a fixed number of colors, C = {1 , 2, ... , m}. Some of the sets mentioned above interfere with each other. I cannot assign same color to both those sets together.

I want to pick the sets and color them from my available color list in the following way:

**Objective: Minimize the total cost of the selected sets

Constraints:

All elements of the universe are covered

No two sets that interfere with each other is assigned the same color**

If the second constraint, i.e., coloring constraint, is taken out, the problem reduces to standard weighted set covering problem. I can solve that using a greedy manner. For example, greedy unweighted set covering will work in the following way: -- 1. pick the set with the highest number of elements at first, 2. Remove that set and the associated elements from the universe, 3. Repeat step 1 until all elements of the universe are covered.

But the coloring constraint in the presence of interference among sets and a fixed number of colors complicates the issue.

For example, let's assume,

U = {1, 2, 3, 4, 5}.

There are three sets, {1, 2, 3}; {2, 3, 4, 5} ; {4, 5}.

Assume {2, 3, 4, 5} interferes with both {1, 2, 3} and {4, 5}. {1, 2, 3} and {4, 5} do not interfere with each other. Assume that there is only one color in the system.

A standard greedy unweighted set coloring solution will pick {2, 3, 4, 5} at first and {1, 2, 3} in the second round. But that is an infeasible solution to my problem since they interfere with each other and I have only one color in my system. A feasible solution will be the selection of {1, 2, 3} and {4, 5}.

I wonder how I can minimize the total cost while meeting the color constraint. Any hint on the unweighted version of the problem (where all sets have equal cost) will be very helpful, too.

Thanks,

Nazmul

Additional information: The coloring of the sets and the interference can be understood by my application scenario.

I am looking at a wireless cell. I have a set of frequencies, possible base station locations and their associated users. Each set is associated with a station and it shows the set of users that the base station can serve.

"Interference" from one set to the other means that the users' signals of one set reaches the other set's base station. In a wireless setting, this interference is not symmetric. But assumption of symmetry is OK in the algorithm because if set A interferes with set B, A & B both should get different colors if they are selected.

The interference among sets is not transitive. Set A may interfere with set B (A's users may interfere with B's base station) and set B may interfere with set C (B's users may interfere with C' base station) but that does not mean that set A will interfere with set C.

The current example is showing that two sets interfere if they intersect. This is just a coincidence. I will have a pre-generated look up table that shows which set interferes with which set before the algorithm starts. This pre-generated table will be an input to the optimization problem

Explanation / Answer

Obviously, if the number of colors is fixed, there is not much hope for a polynomial algorithm. You'd have to answer the question, whether your dependency graph G is colorable with n colors, which is NP-hard in general

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.