Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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

share|improve this answer

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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