4
$\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$

1 Answer 1

1
$\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$
5
  • $\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$ Jul 29, 2018 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$ Jul 29, 2018 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$ Jul 29, 2018 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, 2018 at 14:46
  • $\begingroup$ Unfortunately I can't help you with that. $\endgroup$ Jul 29, 2018 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.