MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.