Question: We are given an NP-complete problem, \"given a finit set X and a famil

Question

Question: We are given an NP-complete problem, "given a finit set X and a family of subsets F, find the smallest number of subset covering each piont in X at least once." However, now each set Si in F has weight wi associated with it. we will extend the greedy heuritics to minimize the total weight of the selected Si s' while covering each piont in X.

Typically, the objective function will take the weight of a given set and the number of pionts that it covers. Suppose, we choose to greedily select a set with the smallest ratio of its weight and the number of points (which have not been covered untill now) that the set covers. This will try to minimize the "price" per element. Then the pseudo code will look like:

1. All the pionts are marked as non-covered

2. Selects set with smallest ratio: wi / the largest number of non-covered pionts

3. Once the set is selected, the set's pionts are marked as covered

4. The process repeats itself untill all the points are covered at least once

Answer the following questions:

1. What is the complexity (expressed in big O) for the worst-case scenario of your algorithm, expressed in terms of the number of pionts in X? you do not have to formally compute big O via inequalities.

2. What is the complexity (expressed in big O) for the worst-case scenario of your algorithm, expressed in terms og the number of set Si rather than number of pionts in X? you do not have to formally compute big O via inequalities.

Explanation / Answer

Solution:

Let the number of elements in X be 'n'. Consider a scenario where the weight function F on Si is defined to be 2^k where k is the number of elements in the subset Si

In this scenario, when the proposed greedy algorithm runs, it always finds the singleton subsets to have the least ratio being equal to 1/n, 1/(n-1),..etc. Hence, in this case the algorithm picks 'n' singleton subsets.

a) For the worst case mentioned above, we choose number of singleton subsets equal to the number of points in set X. Hence, time complexity = O(n).

b) For the same worst case scenario, the number of subsets Si is equal to the number of singleton subsets which is again O(n).

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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