# solve weighted set cover through knapsack

 0 Given an algorithm for the Knapsack problem, can you also solve the min set covering problem? Min set covering problem: min \sum_j c_j y_j such that \sum_j s_j y_j >= b y_j \in {0,1} Knapsack problem: max \sum_j c_j y_j such that \sum_j s_j y_j <= b y_j \in {0,1} ================================ Answer (As per Sune's recommendation below): 1. Substitute every y_j by 1-z_j in the set covering problem. min \sum_j c_j (1-z_j) such that \sum_j s_j (1-z_j) >= b z_j \in {0,1} rewriting and rearranging these constraints yields: max \sum_j c_j z_j - sum_j c_j such that \sum_j s_j z_j <= \sum_j s_j - b z_j \in {0,1} This problem is indeed the desired knapsack problem. the "- sum_j c_j" term in the objective is a constant and can therefore be ignored. After solving this knapsack problem, one can obtain a feasible solution to the set cover problem by setting y_j=1-z_j. Interpretation: Let c_j be the value or cost of an item j, and s_j its weight. The knapsack problem tries to select the most expensive items while keeping their total weight equal or below \sum_j s_j - b. As a result, the remaining items will be as cheap as possible while having a total weight larger or equal to \sum_j s_j-(\sum_j s_j - b)=b. asked 11 Mar '15, 17:29 Joris Kinable 338●1●2●13 accept rate: 16% You have a binary set covering problem with only one cover constraint? (11 Mar '15, 19:23) Paul Rubin ♦♦ @Joris Your definition of Set Cover is nonstandard. Here is the standard one. (11 Mar '15, 23:12) Austin Buchanan @Austin: you are right. I'm not sure ow to name a problem having such a "cover" constraint. Yet I encounter these fairly frequently. Are you aware of a different name? (13 Mar '15, 15:04) Joris Kinable

 2 Try to just substitute $$y_i=1-z_i$$ in the original problem and remember that $$\max f(x)=-\min-f(x)$$ answered 11 Mar '15, 18:36 Sune 958●4●13 accept rate: 20% Thanks, that indeed is correct. I've updated my question with the answer. (11 Mar '15, 20:42) Joris Kinable
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×13