Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Are set covering problems (set cover problem wikipedia) with a nonlinear cost function also NP-hard? Is there a general result about this?

To be more specific the cost function I am interested in something like:

\begin{equation} C(S)=\sum_{s\in S}[ f(|s|)-ln(n_{|s|}(S))] \end{equation} where S is the cover s are the subsets |s| the size of the set s f some positive strictly increasing cost function that only depends on size and $n_{|s|}(S)$ the number of subsets of size |s| in S.

share|improve this question
add comment

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.