Consider the following optimization problem

INSTANCE: vectors $\vec{a}, \vec{b}, \vec{c}$, matrices $A, B$, threshold $\theta$.


Let $f={\displaystyle \max_{\vec{x}, \vec{y}}} (\vec{x}+\vec{c}) \cdot \vec{y}$

subject to $A\vec{x}\leq \vec{a}$ and $B\vec{y}\leq \vec{b}$

Is $f \le \theta$ ?

This problem is in co-NP (provide a witness that $f > \theta$).

Is this problem in NP ?

  • 1
    $\begingroup$ Can lagranges multiplier method be used to obtain the maximum value? (Just a random thought) $\endgroup$ – Vivek Bagaria Mar 21 '14 at 16:26
  • $\begingroup$ what does $\vec{x}\leq\vec{a}$ mean for vectors $\vec{x}$ and $\vec{a}$? $\endgroup$ – Brout Mar 21 '14 at 21:37
  • $\begingroup$ it's a componentwise comparison: shorthand for a set of inequalities. $\endgroup$ – Suresh Venkat Mar 22 '14 at 8:09

Your Answer

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

Browse other questions tagged or ask your own question.