2
$\begingroup$

Consider a parallelotope in R^n and some point "P" in R^n. What algorithms (except of brute force) can be suggested to find the closest vertex of paralleloptope to "P" ?

Is it NP ?

Parallelotope has 2^n vertex, not arbitrary 2^n point in R^n are vertex of paralleloptope, so clever algorithm should somehow use this additional information, while brute force search over 2^n points does not use.

==

Reformulation:

after choosing origin in the center of parallelotope we can come to the following algebraic version of the problem: minimize over x_i = {-1,+1} the quadratic form: \sum a_ij x_i x_j - \sum x_i v_i

$\endgroup$

2 Answers 2

3
$\begingroup$

This looks almost like the Max-CUT problem to me (you have minimize instead of maximize, but you can just flip the signs of the matrix $A$)

In general, you problem is an instance of a binary quadratic program, so it will be hard to solve. Have a look at some solvers on this webpage

$\endgroup$
1
$\begingroup$

This is equivalent to the MIMO detection problem, which is NP hard. Here is a paper with a semidefinite relaxation: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.163.3233&rep=rep1&type=pdf

Then, there exist some easy instances of the problem, if your matrix of the quadtratic form is negative semidefinite and rank deficient. Check these for example

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.594&rep=rep1&type=pdf

http://www.telecom.tuc.gr/~karystinos/paper_TIT3.pdf (algorithm included)

$\endgroup$

Your Answer

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

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