2
$\begingroup$

I am trying to solve a weighted set cover problem where the number of selected subsets is limited by a constant $k$. Assuming this is a pretty straight-forward variation of weighted set cover I ended up quite confused with only one, also rather recent paper by Golab et al. [1].

Am I missing something here?

[1] Golab, Korn, Li, Saha and Srivastava, Size-constrained weighted set cover. In _Proceedings of 31st International Conference on Data Engineering (ICDE), pp. 879–890. IEEE, 2015. IEEE Digital Library; author PDF.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Welcome to CS.SE! 1. Can you edit the question to provide a reference that will be as robust over time as possible? We have collected some advice here. I suggest including the title, authors, and where it was published. 2. What exactly do you want to know about the problem? 3. If you can find one paper on a topic, it's often useful to check what other papers cite that one and what other papers it cites, to see if any of them have anything relevant. $\endgroup$ – D.W.♦ Jan 28 '17 at 12:28
2
$\begingroup$

The problem is in P and can be solved in $O(m^k)$ time, where $m$ is the number of sets to select from. For this reason, it is fundamentally different from standard set cover (which is NP-hard) and might not have been studied as much in the complexity theory literature.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer. Can you please provide some link or reference? In the paper mentioned above the authors show NP-hardness in IV COMPLEXITY ANALYSIS for their problem. $\endgroup$ – martin Jan 29 '17 at 7:56
  • $\begingroup$ @martin, in that paper, $k$ is part of the input, rather than a constant. When $k$ is part of the input (i.e., unbounded), the problem is NP-complete. When $k$ is fixed (e.g., 5), it is in P. $\endgroup$ – D.W.♦ Jan 30 '17 at 4:08

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.