<p>Consider a graph $G=(V,E)$. Define the set function $f$ over $V$ where $f(A)$ is the number of edges with both end points in $A$. Then $f$ is supermodular and monotone. Suppose $G$ has an independent set of size $k$. Then the minimum of $f(S)$ under the constraints $|S| = k$ (the uniform matroid constraint) will be $0$. If $G$ does not have an independent set of size $k$ then the min will be at least $1$. Hence the problem is inapproximable.</p>

CC BY-SA 3.0
2018-02-13T00:54:50.623Z
2018-02-13T00:54:50.623Z
Chandra Chekuri
<p>Is there a known approximation algorithm for the problem of minimizing 
a monotone (non increasing) supermodular function under partition matroid constraints ?</p>

<approximation-algorithms><optimization><submodularity>
Monotone supermodular function minimization under partition matroid constraints
Gilad
# Monotone supermodular function minimization under partition matroid constraints

(Asked by: username_0 on 2018-02-12)

Is there a known approximation algorithm for the problem of minimizing
a monotone (non increasing) supermodular function under partition matroid constraints ?

**Tags:** approximation-algorithms, optimization, submodularity


---

## 1 answers

### Answer by username_1 on 2018-02-13. Score: 2 | Accepted answer

Consider a graph $G=(V,E)$. Define the set function $f$ over $V$ where $f(A)$ is the number of edges with both end points in $A$. Then $f$ is supermodular and monotone. Suppose $G$ has an independent set of size $k$. Then the minimum of $f(S)$ under the constraints $|S| = k$ (the uniform matroid constraint) will be $0$. If $G$ does not have an independent set of size $k$ then the min will be at least $1$. Hence the problem is inapproximable.


---

