# Complexity of maximising weighted sum of and functions on a set of binary variables

Suppose we have a set of binary variables $a_1, ..., a_n$ that $a_i\in\{0,1\}$. Now we define $m$ and functions over a subset of them: $$j\in\{1,...,m\}: f_j=x_1\land x_2\land...\land x_k$$ in which $$\{x_1,...,x_k\}\subset\{a_1,...,a_n\}$$

Suppose that each variable $a_i$ has also a cost $c_i$ assigned to it and every function $f_j$ has a profit $p_j$ associated with it. Both variables are non-negative $\forall i,j: p_j,c_i\ge 0$.

The problem is how to maximise profits minus costs over the set of all possible $a_i$s: $$(1) \max_{a_1,...,a_n} \left\{\sum_j^m p_j f_j - \sum_i^n c_i a_i \right\}$$

Another related problem is to maximise the profit with constrained costs for some constant $C$: $$(2) \max_{\sum_i c_i a_i \le C} \left\{\sum_j^n p_j f_j \right\}$$.

Now here here the questions I have:

1. Can $(1)$ be solved in a strictly polynomial, or pseudo-polynomial way?
2. Can $(2)$ be solved in pseudo-polynomial time?

By pseudo-polynomial we mean assuming bounds on $|c_i|$ and $|p_j|$, can a polynomial time algorithm be achieved?

It's clear that if $(2)$ pseudo-polynomial solution $(1)$ will also have a pseudo-polynomial solution, by iterating over various values of $C$. Therefore in some sense $(2)$ is a more difficult problem. Moreover, knapsack can be seen as a special case of $(2)$ if we set $f_j=a_j$. Therefore it can't be strictly polynomial. But I can't tell much more about the complexity of these two problems.

• The version of the knapsack problem you described (with $f_j = a_j$) can be easily solved, you simply set $a_i = 1$ if $c_i \ge p_i$ and set $a_i = 0$ otherwise. Jan 7, 2018 at 12:34
• @ArturRyazanov you are right, so maximising the difference is an easier problem than the original knapsack, which is only pseudo polynomial. Jan 7, 2018 at 15:13
• $k-\mathrm{CLIQUE}$ can be reduced to (2). Create a variable for each vertex, set all $c_i = 1$, $C=k$ and for each edge $(u,v)$ add the function $u \land v$ with $p=1$. The answer for this instance of (2) equals $\binom{k}{2}$ iff the given graph has $k$-CLIQUE. Thus (2) has no pseudo-polynomial algorithm. Jan 7, 2018 at 18:04
• One could do the same for (1): for a case that $f_j$s have only two operands construct a similar graph, $c_i$ cost for vertex $i$ and $p_{ij}$ profit for edge $e(i,j)$ if it exists. Then the problem becomes: choose a subset of vertices with the biggest profit-cost margin. Is this a studied problem, or related to a studied problem? Jan 7, 2018 at 18:45
• I think (1) is, in fact, polynomially-solvable (not completely sure though), I've updated my answer. Jan 7, 2018 at 18:48

(1) has a polynomial solution. Consider a graph with source $s$, sink $t$, vertices $U$ corresponding to the variables and vertices $V$ corresponding to the functions. If $f_j = x_1 \land \ldots \land x_k$ then add edges $f_j \to x_i$ for each $i \in \{1,\ldots,k\}$ with capacities equal to $C$ for $C > \sum p_j$. Add edges $x_i \to t$ with capacities $c_i$ and edges $s \to f_j$ with capacities $p_j$. Consider minimum cut between $s$ and $t$ in this graph (it could be easily found with almost any maximal-flow algrorithm). Let $U_s \subseteq U$ and $V_s \subseteq V$ be the sets of vertices in the component of $s$. Then the value of the minimum cut is $$\sum\limits_{i \in U_s} c_i + \sum\limits_{j \not\in V_s} f_j = \underbrace{\sum\limits_{j\in V} f_j}_{\text{constant}} - \underbrace{\left(-\sum\limits_{i \in U_s} c_i + \sum\limits_{j \in V_s} f_j\right)}_{\text{objective function}}$$ Thus if this value is minimised, the objective function is maximised. On the other hand $U_s$ and $V_s$ for minimum cut have the property that if $x_1 \land \ldots \land x_k = f_j \in V_s$ then $x_1, \ldots, x_k \in U_s$ since otherwise the value of the cut is $\ge C$ which is not optimal. Thus setting $x=1$ for $x \in U_s$ and $x=0$ for $x \not\in U_s$ gives an optimal solution for (1).
The case with arbitrary $p_j$ is $\mathbf{NP}\text{-}\mathrm{complete}$ even with polynomially-bounded $|p_j|$.
If you allow $p_j$ to be negative, you can reduce $\mathrm{max}\text{-}\mathrm{SAT}$ to this problem. For each variable $x_i$ of $\mathrm{max}\text{-}\mathrm{SAT}$ add two variables $x_i$ and $\lnot x_i$ to your input. For each of these pair add the condition $x_i \land \lnot x_i$ with the cost $-C$ for a large enough constant $C$. For all clauses of $\mathrm{max}\text{-}\mathrm{SAT}$ input add the corresponding conjunction with all literals reversed: $x \lor \lnot y \lor z$ becomes $\lnot x \land y \land \lnot z$ (here $\lnot x$ and $\lnot z$ are variables in the new problem). $\lnot x \land y \land \lnot z \iff \lnot (x \lor \lnot y \lor z)$ therefore each unsatisfied conjunctions correspond to satisfied clauses. Thus you can set the cost $p$ for each conjunction as $-1$. For $c_i = 0$ for all $i \in \{1,\ldots, n\}$, $m -\max \left\{\sum\limits_j f_j p_j - \sum\limits_i a_i c_i\right\}$ (where $m$ is the number of clauses in the $\mathrm{max}\text{-}\mathrm{SAT}$ instance) is the maximum number of clauses that could be satisfied in the instance of $\mathrm{max}\text{-}\mathrm{SAT}$ or a value greater than or equal to $C - n$ if the instance is unsatisfiable. Thus $C = 3n$ is "big enough". I.e. for negative $p_j$ there is no polynomial solution even with bounded $|p_j|$ and $|c_j|$ unless $\mathbf{P} = \mathbf{NP}$.