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
