<p>Maximizing a general monotone submodular function $f$ under the constraint that $|S|\leq k$, can be approximated to $(1-1/e)$.  I am wondering if a better approximation algorithm exists if the function $f$ has these additional properties for any element $x$ and subset $S$:</p>

<ol>
<li>$f(\{x\}) \in \{0, 1, 2\}$</li>
<li>$f(S \cup \{x\}) - f(S) \in \{0, 1, 2\}$</li>
</ol>

<p>or even the more restricted properties : </p>

<ol start="3">
<li>$f(\{x\}) \in \{0, 1\}$</li>
<li>$f(S \cup \{x\}) - f(S) \in \{0, 1\}$</li>
</ol>

CC BY-SA 3.0
2014-11-06T04:36:06.167Z
Note that (1) implies (2) (assuming $f(\emptyset) = 0$) since $f(S \cup \{x\}) \leq f(S) + f(\{x\})$. (That's assuming that the function is integer-valued.)
Yuval Filmus
CC BY-SA 3.0
2014-11-06T06:08:54.470Z
(3) implies (4). If a monotone $f$ satisfies (3) then it is essentially the rank function of a matroid $M$ (we can suppress the elements $x$ with $f(x) = 0$). Maximizing $f$ subject to a cardinality constraint is the same as finding min of $k$ and the rank of $M$ which is poly-time solvable.
Chandra Chekuri
<approximation-algorithms><submodularity>
Maximizing a submodular function with restricted values
George Octavian Rabanca
# Maximizing a submodular function with restricted values

(Asked by: username_0 on 2014-11-05)

Maximizing a general monotone submodular function $f$ under the constraint that $|S|\leq k$, can be approximated to $(1-1/e)$. I am wondering if a better approximation algorithm exists if the function $f$ has these additional properties for any element $x$ and subset $S$:

1. $f(\{x\}) \in \{0, 1, 2\}$
2. $f(S \cup \{x\}) - f(S) \in \{0, 1, 2\}$

or even the more restricted properties :

3. $f(\{x\}) \in \{0, 1\}$
4. $f(S \cup \{x\}) - f(S) \in \{0, 1\}$

**Tags:** approximation-algorithms, submodularity

> **Comments:**
> **username_1**: Note that (1) implies (2) (assuming $f(\emptyset) = 0$) since $f(S \cup \{x\}) \leq f(S) + f(\{x\})$. (That's assuming that the function is integer-valued.)  
> **username_2**: (3) implies (4). If a monotone $f$ satisfies (3) then it is essentially the rank function of a matroid $M$ (we can suppress the elements $x$ with $f(x) = 0$). Maximizing $f$ subject to a cardinality constraint is the same as finding min of $k$ and the rank of $M$ which is poly-time solvable.  

---

## 0 answers

