I'm currently working on a linear time heuristic for the rectangle decomposition of a binary matrix. This problem has a polynomial time solution, which in our case is too slow for large-scale processing. I devised a linear time heuristic and I would like to characterize its approximation ratio and the problem is that I'm not familiar with approximations algorithms.
In this paper, Kalinowski proved that there is no integrality gap for this problem. What consequences does this result have? Does it mean that is impossible to design an approximation algorithm?