A store trying to analyze the behavior of its customers will often maintaina two

Question

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

Explanation / Answer

Diverse Subset Problem is NP: Given a set of k customers, it can be checked in polynomial time that no 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

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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