In the Greedy algorithm for the minimum set cover problem, how is the…
2025
In the Greedy algorithm for the minimum set cover problem, how is the cost-effectiveness of a set S defined during an iteration?
- A.
Cost(S) / |S|
- B.
Cost(S) / |C|, where C is the set of already covered elements
- C.
Cost(S) / |S - C|, where C is the set of already covered elements
- D.
|S - C| / Cost(S)
Attempted by 50 students.
Show answer & explanation
Correct answer: C
In the greedy algorithm for minimum set cover, cost-effectiveness is defined as the ratio of newly covered elements to the set's cost. Specifically, it calculates |S - C| / Cost(S), where S is the set and C represents already covered elements. This metric prioritizes sets that maximize new coverage per unit cost.