the following link Maximizing a monotone supermodular function s.t. cardinality says no kind approximation possible for maximizing non negative supermodular function subject to maximum cardinality constraint. Can anyone suggest any reference papers or proof for the above problem.

  • $\begingroup$ Doesn't the accepted answer to the problem you've linked to give an example that apparently proves that no approximation is possible? Doesn't that answer your question? $\endgroup$ – Neal Young Jun 22 '18 at 11:23
  • $\begingroup$ I am asking for help to find reference papers which shows formal proof for the above problem to cite, which I couldn't find. Thanks in advance. $\endgroup$ – user49739 Jun 26 '18 at 4:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.