A store trying to analyze the behavior of its customers will often maintain a two-dimensional array...

 

Transcribed Image Text:

A store trying to analyze the behavior of its customers will often maintain a two-dimensional array A, where the rows correspond to its customers and the columns correspond to the products it sells. The entry A[i, j] specifies the quantity of product j that has been purchased by customer i. Here's a tiny example of such an array A. liquid detergent beer diapers cat litter Raj 6 Alanis Chelsea 7 One thing that a store might want to do with this data is the following. Let us say that a subset S of the customers is diverse if no two of the of the customers in S have ever bought the same product (i.e., for each product, at most one of the customers in S has ever bought it). A diverse set of customers can be useful, for example, as a target pool for market research. We can now define the Diverse Subset Problem as follows: Given an m x n array A as defined above, and a number k < m, is there a subset of at least k of customers that is diverse? 1. (7 points) Show that Diverse Subset is in NP. 2. (18 points) Show that Diverse Subset is NP-complete. A store trying to analyze the behavior of its customers will often maintain a two-dimensional array A, where the rows correspond to its customers and the columns correspond to the products it sells. The entry A[i, j] specifies the quantity of product j that has been purchased by customer i. Here's a tiny example of such an array A. liquid detergent beer diapers cat litter Raj 6 Alanis Chelsea 7 One thing that a store might want to do with this data is the following. Let us say that a subset S of the customers is diverse if no two of the of the customers in S have ever bought the same product (i.e., for each product, at most one of the customers in S has ever bought it). A diverse set of customers can be useful, for example, as a target pool for market research. We can now define the Diverse Subset Problem as follows: Given an m x n array A as defined above, and a number k < m, is there a subset of at least k of customers that is diverse? 1. (7 points) Show that Diverse Subset is in NP. 2. (18 points) Show that Diverse Subset is NP-complete.

Answer rating: 100% (QA)

1 To prove that Diverse Subset is in NP a polynomial time verifier for Diverse Subset is Inputs A1m ... View the full answer