1
$\begingroup$

I am new to submodular functions and I am reading the introductions to submodular functions and applications ( https://www.ima.umn.edu/optimization/seminar/queyranne.pdf ).

In this introduction, it says

" A submodular set function can be minimized in strongly polynomial time. Remark: • minimizing a submodular function f, subject to a cardinality constraint, such as |A| = b, or |A| ≥ b, or |A| ≤ b are NP-hard when f is a cut function ".

In the remark, it says the problem is NP-hard if 1) there is a cardinality constraint and 2) f is a cut function.

What if only one of the 2 constraints holds, i.e. f is not a cut function but there is a cardinality constraint? Is this problem of minimizing f(A) still an NP-hard problem?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Starting with a cut function, you can modify one value of the function (say $f$ of the entire universe) without modifying the objective value while keeping the function submodular. So asking that $f$ not be a cut function doesn't make the problem easier. $\endgroup$
    – Yuval Filmus
    Mar 11, 2015 at 13:27
  • $\begingroup$ @YuvalFilmus Hence the be f a cut function or not, the size-constrained minimizing submodular function is NP-hard. $\endgroup$
    – Jerry Song
    Mar 12, 2015 at 3:48

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.