1
$\begingroup$

I am looking at the diverse subset problem in Kleinberg and Tardos, shown in the image:

Why can't we give a polynomial time algorithm for this? Cant we iterate through each person a, and then each item i, and then see for each person b $\neq$ a if b has bought item i, then conclude that a and b cannot be diverse? And if we get through all items and no item that a has bought has been bought by b therefore implies they're diverse? Then we do this with each customer. What's wrong with this approach?

Improve this question
$\endgroup$
3
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$
    – Raphael
    Commented Nov 28, 2018 at 22:47
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Commented Nov 28, 2018 at 22:48
  • $\begingroup$ Hint, $k$ could be something like $m/4$. Your brute force searching may run exponential steps. $\endgroup$
    – John L.
    Commented Nov 29, 2018 at 4:45

1 Answer 1

Reset to default
1
$\begingroup$

The algorithm you described isn't polynomial time because it has to consider every possible subset of customers (they are $2^m$ of these).

Solution

This problem is NP-hard because the vertex cover problem can be reduced to it.

https://en.wikipedia.org/wiki/Vertex_cover#Computational_problem

HINT: To do the reduction, consider how you would model $A$ as a graph and vice-versa. Once you've done that, consider how a "diverse set" is related to a vertex cover in the graphs.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.