A store trying to analyze the behavior of its customers will often maintaina two-dimensional array A, where the rows correspond to its customersand 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.

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 theof the customers in S have ever bought the same product (i. e., for eachproduct, at most one of the customers in S has ever bought it). A diverseset of customers can be useful, for example, as a target pool for marketresearch.

We can now define the Diverse Subset Problem

Question

Guest

Computers & Technology

24 July, 10:51

A store trying to analyze the behavior of its customers will often maintaina two-dimensional array A, where the rows correspond to its customersand 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.

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 theof the customers in S have ever bought the same product (i. e., for eachproduct, at most one of the customers in S has ever bought it). A diverseset of customers can be useful, for example, as a target pool for marketresearch.

We can now define the Diverse Subset Problem

+2

Answers (1)

Know the Answer?

Kenneth Ritter · Answer 1

See explaination

Explanation:

Diverse Subset Problem is NP: When presented with a set of k customers, it can be checked in polynomial time that you wont at any time have two customers in the set have ever bought the same product.

Independent Set is known to be NP-complete.

Independent Set? P Diverse Subset Problem: Suppose we have a black box for Diverse Subset Problem and want to solve an instance of Independent Set. For our Independent Set Problem, we have a graph G = (V, E) and a number k, and need to find out if G contains an independent set of size (at least) k. We need to reduce the Independent Set Problem to a Diverse Subset Problem. We do this by constructing an array where each v in V is a customer and each e in E is a product, and customer v purchased every product e for which the product edge e touches the customer node v. Then we ask the black box for the Diverse Subset Problem if there is a subset of k customers that is diverse.

The black box for the Diverse Subset Problem will return.