2
$\begingroup$

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!

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Apr 18, 2022 at 8:08
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 19, 2022 at 2:03
  • $\begingroup$ @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. $\endgroup$ Commented Apr 19, 2022 at 6:01
  • $\begingroup$ @ChandraChekuri Ah yes, they should be non-negative. Thanks! $\endgroup$ Commented Apr 19, 2022 at 6:10
  • $\begingroup$ 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. $\endgroup$ Commented Apr 21, 2022 at 1:23

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you, you have fully answered this question $\endgroup$ Commented May 3, 2022 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.