Counting magic squares in quasi-polynomial time

Details Counting magic squares in quasi-polynomial time Counting magic squares in quasi-polynomial time

2007-03-08

arxiv.org/abs/math/0703227v1

Mathematics

Combinatorics

30 pages

Scientific paper

We present a randomized algorithm, which, given positive integers n and t and a real number 0< epsilon <1, computes the number Sigma(n, t) of n x n non-negative integer matrices (magic squares) with the row and column sums equal to t within relative error epsilon. The computational complexity of the algorithm is polynomial in 1/epsilon and quasi-polynomial in N=nt, that is, of the order N^{log N}. A simplified version of the algorithm works in time polynomial in 1/epsilon and N and estimates Sigma(n,t) within a factor of N^{log N}. This simplified version has been implemented. We present results of the implementation, state some conjectures, and discuss possible generalizations.

Affiliated with

Also associated with

No associations

Rating

Counting magic squares in quasi-polynomial time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting magic squares in quasi-polynomial time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting magic squares in quasi-polynomial time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-642791