1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.