I have a set function $f:2^V\rightarrow R_+ $which is non negative monotone supermodular function with a property that $f(\{x\})$ is same for all $x\in V$($f(\{x_1\})=f(\{x_2\})=\dots =f(\{x_i\}),\forall x_i\in V)$. I want to maximize this function with maximum cardinality constraint, in other words, to maximize $f(S)$ over all subsets $S$ of size at most $k$, where $k$ is given as input.

From Maximising monotone supermodular functions s.t. cardinality, there will be no kind of approximation is possible except with exponential(k) value queries. But in this problem, a simple greedy algorithm always gives the optimal value. I couldn't find the reason for this. I tried computing submodularity ratio, supermodular curvature to find greedy bounds. Both measures giving poor bounds for greedy but simulations show greedy always performing better. I don't know what to call about the property I mentioned above. Is anyone explored about this property especially for finding bounds for greedy?

  • 1
    $\begingroup$ Doesn't the answer in the post you linked to give a counter-example in your model? That is, it gives a super-modular function $f$ where $f(\{x_i\}) = 0$ for all $i$, thereby satisfying your condition, and such that there is only one subset $S$ of size $k$ or less that gives $f$ a non-zero value, so that finding that set would take exponentially many queries (and greedy certainly can't do it). $\endgroup$ – Neal Young Mar 13 at 20:30
  • $\begingroup$ That example is talking about all subsets of cardinality less than k is same except few. Mine is different. For example if my ground set is $V={1,2,3,4}, f(1)=f(2)=f(3)=f(4)$ but $f(1) \notequal f({1,2})$.It also has some other symmetries such as $f(i,j)=f(j,i) \forall i,j \in V$. My question is, is there any results for greedy performance based on the properties of ground set rather than properties of set function say submodularity ratio and curvature. $\endgroup$ – user49739 Mar 14 at 4:33
  • $\begingroup$ I think your question is not yet precise enough to be answered. For example, one could easily modify the example in the post you linked to (by perturbing the values slightly) so that most values of $f$ are distinct, so as to meet the condition $f(\{i\})\ne f(\{i,j\})$ for all $i, j$ with $i\ne j$. And what precisely do you mean by "properties of ground set"? $\endgroup$ – Neal Young Mar 14 at 11:37

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.