Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

I have an algorithm that on all examples I was running finds an arbitrary approximation of global minimum of binary quadratic program. The algorithm find the minimum in polynomial time. Binary quadratic program is NP-complete, and I cannot prove theoretically, that the algorithm always finds the right solution (it always does in practice). The memory requirement for the algorithm is in current implementation $ n^8 $, where n is the dimension of the problem, it can be reduced to $ n^4 $ leading to possibility to solve the problem in about 50 dimensions, although running time is large - the algorithm have to solve the semi-definite program in $ n^4 $ dimension.

Question:
Is there any practical application this algorithm can be used?
What benchmarks tests should be performed to demonstrate practical usefulness of the algorithm?

I'm not sure I'm allowed to post the link, so you can find details of the algorithm, and its python implementation though the link in my profile, or here, if link works.

PS. I apologize if this is off topic question, I got algorithm by a complete chance, and have no idea where and how to communicate it.

PPS. I know it goes completely against the public opinion, but this is a testable objective, so give it a chance to survive, at least to the moment when it finds counterexample, or can be used as a practical application without a proof.

share|improve this question
Silly comment: I have learned that BQP does not always mean bounded-error quantum polynomial time. – Tsuyoshi Ito Jan 31 '11 at 18:34
BQP is removed. – mkatkov Jan 31 '11 at 18:37
Oh. I did not mean “Do not use the word BQP for other meanings than what I know!” – Tsuyoshi Ito Jan 31 '11 at 20:18
I was kicked to death by the experts, so I prefer to follow any expert's advise, that does not change meaning, to get something useful. – mkatkov Jan 31 '11 at 20:27
You could outline your idea here to give people an idea of what you are talking about. Also, your statement "if it cannot be proved it can be used" (from your blog) disturbs me. – Raphael Jan 31 '11 at 23:14
show 1 more comment

1 Answer

up vote 4 down vote accepted

The Biq Mac library provides a collection of instances four your problem.

share|improve this answer
(!) The approximation and heuristic methods works in the problem space, and not in the quadratic monomial space, that means they will always outperform. I read it as there is no practical application for exact algorithm, that is slower then approximated one. (!!) Therefore exact algorithm is interesting only when there is a proof it is exact, then I do not see how to communicate the observation :(. – mkatkov Feb 1 '11 at 14:26

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.