1
$\begingroup$

I'm wondering if anyone has experience trying to solve a weighted set cover problem over the power set (i.e. all possible subsets) of an $n$-element ground set where the number of sets included in the cover is limited by some constant $k$.

This post indicates that the problem is in $\mathcal{P}$ with running time $\mathcal{O} (m^k)$ where $m$ is the number of subsets to choose from; in my setting $m=2^n$, meaning that the given run-time would be exponential in $n$. I am wondering if this problem can be solved in time polynomial in $n$, the size of the ground set.

I have not come across any publications addressing this problem outside of the one referenced in the link above.

$\endgroup$
  • $\begingroup$ You have to specify the weight for each subset, so the input size is at least $m=2^n$, which means the run-time is polynomial in input size. $\endgroup$ – xskxzr Feb 1 at 10:01
  • $\begingroup$ In the setting I'm exploring (a machine scheduling problem), a subset's weight is computed as a function of parameters of its elements (e.g. $w_S=\sum_{j\in S} p_j$ where $p_j$ is the processing time of job $j$), meaning weights needn't be inputted directly. What I'm really wondering is whether or not this problem's run-time is polynomial in $n$, the size of the ground set. $\endgroup$ – W. Lassiter Feb 1 at 15:26
  • $\begingroup$ Suppose that $k = 2$, and the weights are given as an oracle. Suppose that there exists a secret subset $S$ such that $w(S) = w(\overline{S}) = 0$ and $w(T) = \infty$ for all other sets. There is no approximation algorithm that uses less than $2^{n-1}$ queries in the worst case. $\endgroup$ – Yuval Filmus Feb 1 at 16:20
  • $\begingroup$ Agreed, but what if the weight function is deterministic given the composition of the set? In particular, suppose that each element $j$ of the ground set has a parameter $p_j$ and the weight of a set $S=\{j_1,j_2,\dots,j_t\}$ is given by some (not necessarily linear) function $f(p_{j_1},p_{j_2},\dots,p_{j_t})$. My guess is that the complexity would depend on the nature of $f$ in this case? $\endgroup$ – W. Lassiter Feb 1 at 18:15
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – D.W. Feb 1 at 23:36

Your Answer

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

Browse other questions tagged or ask your own question.