# Solving the Size-Constrained Weighted Set Cover Problem

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.

• 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. – xskxzr Feb 1 at 10:01
• 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. – W. Lassiter Feb 1 at 15:26
• 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. – Yuval Filmus Feb 1 at 16:20
• 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? – W. Lassiter Feb 1 at 18:15
• en.wikipedia.org/wiki/… – D.W. Feb 1 at 23:36