NP difícil (como KNAPSACK) - algum esquema de aproximação?

Question

Para um determinado conjunto $S = \{1, 2, ... , N \}$, cada componente $i\in S$ pode ser representado por um triplo $(a_i, b_i, c_i)$. Como pode o seguinte ser resolvido? Existe algum algoritmo de tempo polinomial?

$$\max_{S' \subseteq S} \left(\sum_{k\in S'} a_k \right) \cdot \left(\sum_{k\in S'} b_k \right) $$ sujeito a $$\sum_{k\in S'} c_k \leq C. $$

Se a função objetivo é $\sum_{k\in S'} a_k$, é KNAPSACK e há um algoritmo polinomial eficiente. Não tenho ideia se existe algum método para resolver esse tipo de problema.

Answer 1

Você pode resolver esse problema da mochila quadrática por meio da programação linear inteira da seguinte maneira. Para$i\in S$, deixe a variável de decisão binária $x_i$ indique se $i\in S'$. Para$1\le i < j \le N$, deixe a variável de decisão binária $y_{i,j}$ representar $x_i x_j$. O problema é maximizar $$\sum_i a_i b_i x_i + \sum_{i < j} (a_i b_j + a_j b_i)y_{i,j}$$ sujeito a \ begin {align} y_ {i, j} & \ le x_i && \ text {para todos$i<j$} \ tag1 \\ y_ {i, j} & \ le x_j && \ text {para todos $i<j$} \ tag2 \\ y_ {i, j} & \ ge x_i + x_j - 1 && \ text {para todos $i<j$} \ tag3 \\ \ sum_i c_i x_i & \ le C \ tag4 \ end {alinhar} Se tudo$a_i$ e $b_i$ são não negativos, você pode omitir $(3)$.