# Maximize a special monotone submodular function - is it easier?

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!

• I wonder if there is a connection to the knapsack problem: with the objective function $g_1(c_1 \cdot x) + g_2(c_2 \cdot x)$ and appropriate settings of $g_1,g_2$ it seems like you might be able to construct a reduction.
– D.W.
Commented Apr 18, 2022 at 8:08
• Are $c_1,c_2$ non-negative vectors? You can approximate increasing concave functions by piece-wise linear functions. After that, if you can do some discretization tricks and via dynamic programming I would think a PTAS/FPTAS would follow. Whether the problem is NP-Hard via Knapsack is not yet clear. Commented Apr 19, 2022 at 2:03
• @D.W. Thanks for this idea. Let the capacity of the sack be $B$. Setting $c_1$ to be the values of the items and $c_2$ to be the sizes, and $g_1(x) = x$ and $g_2$ to be 0 if $x < B$ and $-\infty$ otherwise is the knapsack problem. However, our $g_2$ isn't concave. Also, my problem involves the same function $g$ in both terms, though your generalization might be interesting in it's own right. Commented Apr 19, 2022 at 6:01
• @ChandraChekuri Ah yes, they should be non-negative. Thanks! Commented Apr 19, 2022 at 6:10
• Suppose all numbers in $c_1,c_2$ are integers and polybounded in $n$, the number of items. Then one can find, via DP, all values $A,B$ such that there is a subset of k items such that their $c_1$ sum is $A$ and their $c_2$ sum is $B$. We pick the feasible pair $(A,B)$ that gives the maximum value of $g(A) + g(B)$. One should be able to do the standard Knapsack tricks to ensure that the $c_1,c_2$ values are integers and poly-bounded by losing only a $(1-\epsilon)$-factor. Commented Apr 21, 2022 at 1:23

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$$.

• Thank you, you have fully answered this question Commented May 3, 2022 at 6:58