Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

I have the following problem. Given a graph $G=(V,E)$ with node costs, the task is to select a subset of nodes $S$ such that its cost $h(S)$, which is sum of costs of all nodes in S, does not exceed a given parameter $C$ and $|S|$ is maximised. I can express this problem as follows: $$ \max. f=|S|\quad\text{ such that }\quad h(S) \leq C $$ Basically, I want to select as many nodes as possible without exceeding $C$. If I'll choose the nodes with smallest costs, this will maximise the number of nodes in $S$. I want to formally show the equivalence between these two problem: $$ \max. \{f\; |\; h(S) \leq C\} \Longrightarrow \min. \{h(S)\}\quad\text{ and }\quad h(S) \leq C $$ I would really appreciate any suggestions or links/references.

share|improve this question
2  
Why is this problem stated in terms of graphs? It doesn't involve adjacencies or edges at all. Also, the problem on the right makes no sense: the minimum value of $h(S)$ is clearly $0$. The dual problem is more like "minimize $h(S)$ subject to a lower bound on $|S|$". – Erick Wong Jul 15 '12 at 6:07
Thanks for your answer. I have simplified the cost function that involved edge costs as well. You are right, the dual problem should be constrained. Is there a way to show the equivalence between this problem and its dual, i.e., go from max to min? – vn1k Jul 16 '12 at 2:16

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.