<p>I believe that the problem is NP-Hard and it admits a FPTAS. Let me sketch my thoughts.</p>
<p><strong>NP-Hardness:</strong> Consider a slight variant of the well-known 2-Partition problem. Given <span class="math-container">$2n$</span> non-negative integers <span class="math-container">$a_1,a_2,\ldots,a_{2n}$</span> is a there a subset of cardinality <span class="math-container">$n$</span> such that their sum is exactly <span class="math-container">$B = \frac{1}{2}\sum_i a_i$</span>? This is NP-Complete.</p>
<p>Given such an instance we construct two vectors <span class="math-container">$c$</span> and <span class="math-container">$c'$</span> where <span class="math-container">$c_i = a_i$</span> and <span class="math-container">$c'_i = M - a_i$</span> where <span class="math-container">$M$</span> is some sufficiently large number so that <span class="math-container">$c'_i \ge 0$</span> for all <span class="math-container">$i$</span>. Let <span class="math-container">$B_1 = B$</span> and <span class="math-container">$B_2 = nM - B_1$</span>. There is a subset <span class="math-container">$S$</span> of <span class="math-container">$[2n]$</span> such that <span class="math-container">$|S| = n$</span> and <span class="math-container">$a(S) = B$</span> iff <span class="math-container">$c(S) = B_1$</span> and <span class="math-container">$c'(S) = B_2$</span>. Moreover, if <span class="math-container">$|S| \le n$</span> then <span class="math-container">$c'(S) \le B_2$</span>.</p>
<p>By scaling <span class="math-container">$c$</span> and <span class="math-container">$c'$</span> by <span class="math-container">$B_1$</span> and <span class="math-container">$B_2$</span> we can normalize <span class="math-container">$B_1$</span> and <span class="math-container">$B_2$</span> to be <span class="math-container">$1$</span>. Then there is a subset <span class="math-container">$S$</span> of <span class="math-container">$[2n]$</span> such that <span class="math-container">$|S| \le n$</span> and <span class="math-container">$a(S) = B$</span> iff <span class="math-container">$c(S) = 1$</span> and <span class="math-container">$c'(S) = 1$</span>.</p>
<p>Now consider the concave function <span class="math-container">$g$</span> where <span class="math-container">$g(x) = \min\{x,1\}$</span>. We consider the original Partition instances and the scaled vectors <span class="math-container">$c,c'$</span> that we generate as above. If the anser to the instance is YES then there is a set <span class="math-container">$S \subset [2n]$</span> such that <span class="math-container">$|S| = n$</span> and <span class="math-container">$a(S) = B$</span> then we have <span class="math-container">$c(S) = 1$</span> and <span class="math-container">$c'(S) = 1$</span>, and hence <span class="math-container">$g(c(S)) + g(c'(S)) = 2$</span>. If there is a subset <span class="math-container">$S$</span> such that <span class="math-container">$|S| \le n$</span> and <span class="math-container">$g(c(S)) + g(c'(S)) = 2$</span> then <span class="math-container">$c(S) = 1$</span> and <span class="math-container">$c'(S) = 1$</span> which then implies that <span class="math-container">$a(S) = B$</span>. Thus the optimum value to the concave maximization problem is <span class="math-container">$2$</span> iff the original 2 Partition instance is a YES instance. This proves NP-Hardness of the optimization problem.</p>
<p><strong>FPTAS:</strong> I sketched it in the comment which is similar to that of Knapsack. Given <span class="math-container">$c,c'$</span> let <span class="math-container">$c''_i = \max(c_i,c'_i)$</span>. Fix some optimum solution. We <em>guess</em> an item in the optimum solution that has the largest <span class="math-container">$c''_i$</span> value. Let this value be <span class="math-container">$B$</span>. Note that <span class="math-container">$OPT \ge g(B)$</span>. Once we guess <span class="math-container">$B$</span> we can assume without of loss of generality that for all items <span class="math-container">$i$</span>, <span class="math-container">$c''_i \le B$</span> by eliminating the others. For each <span class="math-container">$i$</span> we set <span class="math-container">$d_i = \lfloor n c_i/(2 \epsilon B)\rfloor$</span> and <span class="math-container">$d'_i = \lfloor n c'_i/(2 \epsilon B)\rfloor$</span>. Note that <span class="math-container">$d_i$</span> and <span class="math-container">$d'_i$</span> are integers in the range <span class="math-container">$0$</span> to <span class="math-container">$2n/\epsilon$</span> and hence are poly-bounded. This is the standard scaling and rounding process. We say that two numbers <span class="math-container">$X,Y$</span> are feasible if there is a subset <span class="math-container">$S \subset [2n]$</span>, <span class="math-container">$|S| \le n$</span> such that <span class="math-container">$d(S) = X, d'(S) = Y$</span>. We can find all feasible <span class="math-container">$(X,Y)$</span> pairs via DP in time polynomial in <span class="math-container">$n$</span> since the numbers in <span class="math-container">$d,d'$</span> are integers and are at most <span class="math-container">$2n/\epsilon$</span>. We pick the feasible pair <span class="math-container">$(X,Y)$</span> that maximizes the quantity <span class="math-container">$g(2\epsilon B X/n) + g(2\epsilon B Y/n)$</span> and return the corresponding set that achieves <span class="math-container">$(X,Y)$</span>.  This should yield a <span class="math-container">$(1-O(\epsilon))$</span> approximation. The running time is basically dominated by the DP which can be seen to be polynomial in <span class="math-container">$n/\epsilon$</span>.</p>

CC BY-SA 4.0
2022-05-03T06:58:32.857Z
Thank you, you have fully answered this question
Karagounis Z
CC BY-SA 4.0
2022-04-26T21:51:18.310Z
2022-05-14T15:22:09.080Z
2022-05-14T15:22:09.080Z
Chandra Chekuri
<p>I am looking for a way to optimize the function <span class="math-container">$f$</span>, defined below.</p>
<p>First, fix some positive integer <span class="math-container">$k$</span> and let <span class="math-container">$c_1$</span> and <span class="math-container">$c_2$</span> be non-negative vectors in <span class="math-container">$\mathbb{R}^n$</span>. Let <span class="math-container">$g$</span> be an increasing concave function of a single variable.</p>
<p>Now define <span class="math-container">$$f(x) = g(c_1 \cdot x) + g(c_2 \cdot x),$$</span></p>
<p>where <span class="math-container">$x \in \{0,1\}^n$</span> such that <span class="math-container">$\sum_{i=1}^n x_i \leq k$</span>. In other words, I want to maximize <span class="math-container">$f$</span> over all vectors <span class="math-container">$x$</span> which have a 1 in at most <span class="math-container">$k$</span> coordinates and 0 everywhere else.</p>
<p>This is a special case of monotone submodular maximization subject to a cardinality constraint, so there exists an algorithm which yields a <span class="math-container">$(1-1/e)$</span> approximation.</p>
<p>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 <span class="math-container">$(1-1/e)$</span> which runs in time <span class="math-container">$f(k)\cdot O(n^c)$</span>.</p>
<p>Do you think this is possible? Thanks!</p>

CC BY-SA 4.0
2022-04-18T08:08:42.020Z
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.
CC BY-SA 4.0
2022-04-19T02:03:01.080Z
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.
Chandra Chekuri
CC BY-SA 4.0
2022-04-19T06:01:28.723Z
@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.
Karagounis Z
CC BY-SA 4.0
2022-04-19T06:10:17.607Z
@ChandraChekuri Ah yes, they should be non-negative. Thanks!
Karagounis Z
CC BY-SA 4.0
2022-04-21T01:23:32.637Z
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.
Chandra Chekuri
<ds.algorithms><co.combinatorics><approximation-algorithms><optimization><fixed-parameter-tractable>
Maximize a special monotone submodular function - is it easier?
Karagounis Z
# Maximize a special monotone submodular function - is it easier?

(Asked by: username_0 on 2022-04-18)

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!

**Tags:** ds.algorithms, co.combinatorics, approximation-algorithms, optimization, fixed-parameter-tractable

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: @username_1 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.  
> **username_0**: @ChandraChekuri Ah yes, they should be non-negative. Thanks!  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_2 on 2022-04-26. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: Thank you, you have fully answered this question  

---

