I have two 2D arrays: $P[n][s]$ and $C[n][s]$, $s \leq n$.

P contains sets of nodes and $C$ the cost of a set in $P$, e.g. the cost of $P[2][2]$ is $C[2][2]$ and a set $p \in P = \{ s_0, s_1, ..., s_{n-1} \}^q, q \leq n$, e.g. $p=\{s_0, s_3\}$.

For every row I can pick at most one set but in the end the union of the picked sets needs to contain all nodes $\{s_0, s_1, ..., s_{n-1} \}$.

How do I find the least expensive picks in linear time?


If you are able to find the least expensive picks in linear (or even polynomial) time then $P=NP$.

Your problem is a generalization of the set-cover problem: given a set $X$ of items and a collection $S = \{S_1, \dots, S_m \} \subseteq 2^X$ of subsets of $X$, find $S' \subseteq S$ such that $\cup_{S_i \in S'} S_i = X$ and $|S'|$ is minimized.

This is exactly your problem once you set $n=|X|$, $s=1$, $P[i][1] = S_i$, and $C[i][1]=1$.

  • $\begingroup$ Well, that's a pity. I was hoping to solve my earlier problem easily ->cs.stackexchange.com/questions/127227/… $\endgroup$ – rn42v1r Jun 18 '20 at 20:31
  • 1
    $\begingroup$ Yeah, I noticed that this problem was also generalizing your earlier question :) $\endgroup$ – Steven Jun 18 '20 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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