3
$\begingroup$

A weighted set cover problem is:

Given a universe $U=\{1,2,...,n\}$ and a collection of subsets of $U$, $\mathcal S=\{S_1,S_2,...,S_m\}$, and a cost function $c:\mathcal S\to Q^+$ , find a minimum cost subcollection of $\mathcal S$ that covers all elements of $U$.

How to design a deterministic algorithm to solve weighted set cover in $O(2^n)$ (just find the optimum solution)?

If I simply use exhaust searching to look through all possible cover (which is actually equals to $2^m$) and find the one with minimum weight, it will cost $O(2^m)$ but not $O(2^n)$.

$\endgroup$
0
$\begingroup$

Use dynamic programming. For every $i \in [m]$ and every $V \subseteq U$, compute the minimal weight of sets among $S_1,\ldots,S_i$ needed to cover $V$.

Here is pseudocode, which uses $w_i$ for the weight of $S_i$:

  1. Set $T[V][0] \gets \infty$ for all $\emptyset \neq V \subseteq U$, and $T[\emptyset][0] = 0$.
  2. For $i = 1,\ldots,m$:
    • Set $T[V][i] \gets T[V][i-1]$ for all $V \subseteq U$.
    • Set $T[V \cup S_i][i] \gets \min(T[V \cup S_i][i], T[V][i-1] + w_i)$ for all $V \subseteq U$.
  3. Return $T[U][m]$.
$\endgroup$
  • $\begingroup$ Correct me if I'm wrong, but this looks like $O(m 2^n)$ complexity, which can be upper-bounded by $O(2^{2n})$ if you make sure the sets are unique. I don't see how to get this to $O(2^n)$. $\endgroup$ – Matej Lieskovsky Jul 29 '18 at 11:21
  • $\begingroup$ When people say $O(2^n)$, they usually mean $\tilde{O}(2^n)$. The number of sets $m$ is usually much smaller than $2^n$ — say, polynomial in $n$. In that case we get a $\tilde{O}(2^n)$ algorithm. $\endgroup$ – Yuval Filmus Jul 29 '18 at 11:48
  • $\begingroup$ Looking at the literature on exponential time algorithms, it seems that the commonly used notation is $O^*(2^n)$, which hides polynomial factors in both $n$ and $m$. The algorithm I describe clearly runs in $O^*(2^n)$. $\endgroup$ – Yuval Filmus Jul 29 '18 at 12:02
  • $\begingroup$ Thank you very much, but I still wonder if there exist a $O(2^n)$ algorithm even when $m=2^n$. $\endgroup$ – wst Jul 29 '18 at 14:46
  • $\begingroup$ Unfortunately I can't help you with that. $\endgroup$ – Yuval Filmus Jul 29 '18 at 15:14

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.