Consider the following optimization problem, that we call the Fewest T-Shirts Pr
ID: 3689950 • Letter: C
Question
Consider the following optimization problem, that we call the Fewest T-Shirts Problem: You are starting a new phone game review web site. You have a list of all the phone games for which you want reviews. You also have friends that are willing to review the games. Each friend is only an expert in some of the games and not others. You want to have each game reviewed at least once. Once you ask a friend to participate, your friend will review all the games he or she knows about. Unfortunately for you, your friend will also expect a ”free” commemorative T-shirt from your web site. You have a list of the friends, and for each friend, you have the list of games your friend would review. Your goal is to choose which friends to ask to do the reviews, so that you get all the games reviewed while paying for the fewest T-shirts.
(a) Rephrase the problem as a Set Cover problem. What are the elements of the set B that need to be covered? What are the sets Si?
(b) Set Cover is an NP-complete problem. The Clay Foundation has offered a prize of $1,000,000 for the first person who can find a polynomial-time algorithm solving an NP-complete problem, or prove that one does not exist (Really. This is the P vs. NP problem). Argue carefully that the Fewest T-shirts problem is at least as hard as Set Cover, so that if you find a polynomial-time algorithm for it, you should get the $1,000,000 prize. (hint: what if someone gave you an arbitrary Set Cover problem? Could you turn it into Fewest T-shirts problem?).
Explanation / Answer
Number of T Shirts - to be minimized
Number of games to be reviewd - to be maximized
Set Cover Problem:
This is used in Combinatorics and compleity theory of computer science.
Karp's 21 NP-Complete problems were proved to be NP_Complete in the early 1970s
Let the Universe be the set of games needing review = {g1, g2, g3, g4, g5, ......, gn}
and the set of T shirts = {t1,t2,t3, ....., tn}
consider a collection G of T sets whose union will equla thre universe
the set cover probem will encompass the process of identifying the minimal sub set sub collection of the the whole Set
After this the the union must = the universe
say the universe U = {g1,g2,g3,g4,g5}
collection of sets S = {g1,g2,g3}, {g2,g4}, {g3,g4}, {g4,g5}}
union of S = U
but the following smaller number of sets can cover all the elements:
{ {g1,g2,g3},{g4,g5}} as it coverse the universe from {g1, g2,g3,g4, and g5}
Upon applying the greedy algorithm we can approximate log base 2 (n) / 2