4
$\begingroup$

I am interested in the hardness of the following question.

Suppose we have a vector of $n$ optimization variables $\mathbf{x} = \langle x_1, . . ., x_n\rangle $ and $m$ vectors $\mathbf{v}_1, . . .,\mathbf{v}_m$ with each $\mathbf{v}_j \in \{-1,1\}$.

Our objective is to maximize the number of nonnegative dot products between $\mathbf{x}$ and each $\mathbf{v}_j$, where each $0\leq x_i\leq 1$.

That is

$$\max_{\mathbf{x}}\sum_{j=1}^n\mathbb{I}[\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0]$$

$$\text{such that} 0\leq x_i \leq 1$$

These constitute linear constraints and I know in general that maximizing the number of satisfied linear constraints is NP, but these constraints differ in two main ways. The first is that none have a bias term, and the second is that each coefficient of the optimization variables is either 1 or -1.

$\endgroup$
  • $\begingroup$ Doesn't $x = 0$ always maximise the objective? $\endgroup$ – Antti Röyskö Jan 6 at 9:23
1
$\begingroup$

As pointed out by Antti Röyskö the solution $\mathbf{x} = 0$ always maximizes the objective function since $\sum_{j=1}^n\mathbb{I}[\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0]$ corresponds to the number of constraints $\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0$ which are satsificed, and $\mathbf{x}$ satifies all constraints.

However, the problem becomes much more interesting if we dont allow degenerate solutions. In fact, by removing $\mathbf{x} = 0$, the problem goes from having a closed form solution, to being NP-hard. It takes a bit of work, but you can actually reduce any integer feasibility program down to your problem.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.