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?

  • 5
    $\begingroup$ This just means that the optimal objective values of the integer program and its LP relaxation are the same. $\endgroup$ – Austin Buchanan Apr 3 '13 at 13:38
  • $\begingroup$ Thank you, does this means that I cannot deduce anything regarding the feasability of an approximation algorithm ? $\endgroup$ – Dju Apr 3 '13 at 16:07
  • 3
    $\begingroup$ you can deduce that solving the LP solves the problem, so it gives an algorithm (but definitely not a linear time one) $\endgroup$ – Sasho Nikolov Apr 3 '13 at 17:17
  • 4
    $\begingroup$ BTW, in terms of simple approximations, the following uses at most $\log n$ factor more rectangles than necessary: at each step choose the rectangle contained in the support of the matrix that covers the most 1's. this is just the greedy approximation for set cover $\endgroup$ – Sasho Nikolov Apr 3 '13 at 17:26
  • $\begingroup$ The paper is indeed very interesting for the newcomer that I am. Since my linear time algorithm follows a greedy approach it is a good example on how to set up upper bounds. Btw I finally understood what integrality means. Thanks a lot Sasho. $\endgroup$ – Dju Apr 3 '13 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.