Download "An Algorithmic Approach for the Zarankiewicz Problem"
(formerly "Algorithmic Approaches for the Zarankiewicz Problem")
published at the 10th International Workshop on Boolean Problems:
(29.10.2012: Some corrections to the printed version, e.g. number of assignments with respect to row and column permutations)
Presentation on Overflow Algorithm (english)
Download Presentation Slides "An Algorithmic Approach for the Zarankiewicz Problem"
Seminar Paper (german)
Download "Algorithmische Betrachtungen zum Zarankiewicz-Problem"
(29.10.2012: "Solution of the Last Open Four-Colored Rectangle-free Grid" and "The Many Formulae for the Number of Latin Rectangles" added to list of literature)
(28.08.2012: number of assignments with respect to row and column permutations in section 1.2 corrected, Table 1.2 extended)
(31.05.2012: proof on relative runtime asymptotic estimation reworked)
(07.05.2012: time benchmarks on page 11 fixed due to "bug")
(13.03.12)
Overflow and Slot-Algorithm
Download Source Code in C++ // including getopt library by Ludvik Jerabek
(06.09.2012): small improvement on row incrementing (~5% speedup) and some code style
(07.05.2012: upper bounds for maximum of subgrids were partially wrong :/)
(13.03.2012)
// The solution matrix "PrevResults" does not contain the optimal value for 16x16 (unknown)
Seminar Paper - LaTeX/Gnuplot/processing
Download Source
(13.03.2012)
----------------------------------------------
During the last few months I have been working on the Zarankiewicz Problem for my seminar paper. My part was to develop some algorithms, and initially I was supposed to do this using CUDA. After some trials I decided to return to the CPU side, because the problem comes from the extremal graph theory. As far as I know it is even a problem to find the locality of such problems. Actually it even was difficult for me to write a decent and exact algorithm on the CPU side.
In my work you will find two algorithms. The first one is the Overflow Algorithm which works non-recursively and returns the global maximum of edges of the C4-saturated subgraph of K(m,n) (complete bipartite graph). Furthermore I show some ideas for optimization, but they are too savagely and make the algorithm inaccurate. Nevertheless, some nice structure information leads to an interesting connection with the slot architecture of the second algorithm.
The second algorithm is a greedy one called Slot Algorithm. The key idea is from B. Steinbach; he is my supervisor in this work. Different structure information had been used, however, the problem insists to be a beast. I could not finish the Slot Algorithm as I would have liked to do. There are many open questions about the bit/edge pattern hierarchy and how bit patterns of different sizes interact with each other.
Related Posts:
Rectangle Free Grid Coloring of 21x12
In my work you will find two algorithms. The first one is the Overflow Algorithm which works non-recursively and returns the global maximum of edges of the C4-saturated subgraph of K(m,n) (complete bipartite graph). Furthermore I show some ideas for optimization, but they are too savagely and make the algorithm inaccurate. Nevertheless, some nice structure information leads to an interesting connection with the slot architecture of the second algorithm.
The second algorithm is a greedy one called Slot Algorithm. The key idea is from B. Steinbach; he is my supervisor in this work. Different structure information had been used, however, the problem insists to be a beast. I could not finish the Slot Algorithm as I would have liked to do. There are many open questions about the bit/edge pattern hierarchy and how bit patterns of different sizes interact with each other.
Related Posts:
Rectangle Free Grid Coloring of 21x12
I have been interested in this problem recently, and I wrote a direct solver which uses row/column symmetries to find exact solutions, but does not depend on any theorems or conjectures.
AntwortenLöschenRow symmetry is used to choose rows in weight order (most 1s to fewest 1s), and rows of equal weight in lexicographic order (with 1 before 0). This gives an upper bound on the weight of a partial grid's completion, which can be used to reject partial grids because the most recent solution can be used as a lower bound.
Column symmetries are used to recursively partition the columns such that the next row in a partial grid has, without loss of generality, 1s followed by 0s within each partition.
Transpose symmetry could be used to require that no column has a weight greater than the weight of the first row, though I didn't implement this.
Results for some small grids are below. Times to find the optimum (and prove it is optimal) are in seconds, from a Java implementation on a 2.4GHz processor:
n,score,time
7,21,0.002
8,24,0.027
9,29,0.107
10,34,11.133
11,39,213.261
This seems considerably more efficient than the algorithm you describe.
If the rows are ordered lexicographically rather than by weight, the algorithm is much slower, but the resulting solutions are in a form analogous to the Paige-Wexler normal form of the incidence matrix of a finite projective plane. This leads to an elegant (and even more efficient) algorithm analogous to using transversals to search for mutually orthogonal Latin squares.
It is good to see, that there is progress on this problem. Although, I am not working on Zarankiewicz/Latin Squares, I am going to work on similar patterns soon (row/column symmetries again). Your approach is indeed better, since symmetries are exploited much better!
LöschenMy algorithm took 34min to finish the search on 11x11 grid, so you achieved a speedup of factor 9.5 for this dimension.
Are you going to share the code? :)
Best Regards and thanks again for your comment!
I might share code for the more efficient algorithm, since the one described in my previous comment does not take advantage of any theorems, does not exploit the full symmetry group, and does no precomputations. The column symmetry reduction I described is fairly simple to implement recursively - call enforceColumnOrdering(0,0,width) each time a row is added. let g(x,y) be the number in the grid at x,y.
AntwortenLöschenenforceColumnOrdering(y, left, right):
-- for(left < x < right):
---- if(g(x-1,y)==0 and g(x,y)==1):
------ reject this partial solution
-- if(row y+1 exists):
---- for(left < x < right):
------ if(g(x-1,y)==1 and g(x,y)==0):
-------- enforceColumnOrdering(y+1,left,x)
-------- enforceColumnOrdering(y+1,x,right)