(Master Seminar Talk) Swarm Intelligence For The Biclique Cover Problem

The Biclique Cover Problem is such an NP-complete problem. The Biclique Cover Problem simply asks for the size of a minimum biclique cover for a given graph. A biclique cover is a set of bicliques, that is, complete connected bipartite graphs, such that every edge of the graph is contained in at least one biclique.

We consider Swarm Intelligence, more precisely a Max-Min Ant System, for the Biclique Cover Problem.

Since there is no commonly used benchmark suite for the Biclique Cover Problem like for the Traveling Salesman Problem, we build our own benchmark suite consisting of Erdős-Rényi random graphs.

To analyze how well our Swarm Intelligence approach performs we design also other heuristics for the Biclique Cover Problem: a greedy algorithm, a Randomized Local Search, a Simulated Annealing and two different genetic algorithms and apply all of them to the self-created benchmark suite.