Maximize a special monotone submodular function - is it easier?

Question

I am looking for a way to optimize the function $f$, defined below.

First, fix some positive integer $k$ and let $c_1$ and $c_2$ be non-negative vectors in $\mathbb{R}^n$. Let $g$ be an increasing concave function of a single variable.

Now define $$f(x) = g(c_1 \cdot x) + g(c_2 \cdot x),$$

where $x \in \{0,1\}^n$ such that $\sum_{i=1}^n x_i \leq k$. In other words, I want to maximize $f$ over all vectors $x$ which have a 1 in at most $k$ coordinates and 0 everywhere else.

This is a special case of monotone submodular maximization subject to a cardinality constraint, so there exists an algorithm which yields a $(1-1/e)$ approximation.

However, I believe there may be better algorithm for this simpler class. Ideally, I seek an exact algorithm or algorithm with a better ratio than $(1-1/e)$ which runs in time $f(k)\cdot O(n^c)$.

Do you think this is possible? Thanks!

Answer 1

I believe that the problem is NP-Hard and it admits a FPTAS. Let me sketch my thoughts.

NP-Hardness: Consider a slight variant of the well-known 2-Partition problem. Given $2n$ non-negative integers $a_1,a_2,\ldots,a_{2n}$ is a there a subset of cardinality $n$ such that their sum is exactly $B = \frac{1}{2}\sum_i a_i$? This is NP-Complete.

Given such an instance we construct two vectors $c$ and $c'$ where $c_i = a_i$ and $c'_i = M - a_i$ where $M$ is some sufficiently large number so that $c'_i \ge 0$ for all $i$. Let $B_1 = B$ and $B_2 = nM - B_1$. There is a subset $S$ of $[2n]$ such that $|S| = n$ and $a(S) = B$ iff $c(S) = B_1$ and $c'(S) = B_2$. Moreover, if $|S| \le n$ then $c'(S) \le B_2$.

By scaling $c$ and $c'$ by $B_1$ and $B_2$ we can normalize $B_1$ and $B_2$ to be $1$. Then there is a subset $S$ of $[2n]$ such that $|S| \le n$ and $a(S) = B$ iff $c(S) = 1$ and $c'(S) = 1$.

Now consider the concave function $g$ where $g(x) = \min\{x,1\}$. We consider the original Partition instances and the scaled vectors $c,c'$ that we generate as above. If the anser to the instance is YES then there is a set $S \subset [2n]$ such that $|S| = n$ and $a(S) = B$ then we have $c(S) = 1$ and $c'(S) = 1$, and hence $g(c(S)) + g(c'(S)) = 2$. If there is a subset $S$ such that $|S| \le n$ and $g(c(S)) + g(c'(S)) = 2$ then $c(S) = 1$ and $c'(S) = 1$ which then implies that $a(S) = B$. Thus the optimum value to the concave maximization problem is $2$ iff the original 2 Partition instance is a YES instance. This proves NP-Hardness of the optimization problem.

FPTAS: I sketched it in the comment which is similar to that of Knapsack. Given $c,c'$ let $c''_i = \max(c_i,c'_i)$. Fix some optimum solution. We guess an item in the optimum solution that has the largest $c''_i$ value. Let this value be $B$. Note that $OPT \ge g(B)$. Once we guess $B$ we can assume without of loss of generality that for all items $i$, $c''_i \le B$ by eliminating the others. For each $i$ we set $d_i = \lfloor n c_i/(2 \epsilon B)\rfloor$ and $d'_i = \lfloor n c'_i/(2 \epsilon B)\rfloor$. Note that $d_i$ and $d'_i$ are integers in the range $0$ to $2n/\epsilon$ and hence are poly-bounded. This is the standard scaling and rounding process. We say that two numbers $X,Y$ are feasible if there is a subset $S \subset [2n]$, $|S| \le n$ such that $d(S) = X, d'(S) = Y$. We can find all feasible $(X,Y)$ pairs via DP in time polynomial in $n$ since the numbers in $d,d'$ are integers and are at most $2n/\epsilon$. We pick the feasible pair $(X,Y)$ that maximizes the quantity $g(2\epsilon B X/n) + g(2\epsilon B Y/n)$ and return the corresponding set that achieves $(X,Y)$. This should yield a $(1-O(\epsilon))$ approximation. The running time is basically dominated by the DP which can be seen to be polynomial in $n/\epsilon$.