<p>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. </p>

<p>In <a href="http://www.math.uni-rostock.de/~kalinowski/papers/dual_rectangle_segmentation.pdf" rel="nofollow noreferrer">this paper</a>, 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?</p>

CC BY-SA 3.0
2013-04-03T13:38:56.967Z
This just means that the optimal objective values of the integer program and its LP relaxation are the same.
Austin Buchanan
CC BY-SA 3.0
2013-04-03T16:07:18.497Z
Thank you, does this means that I cannot deduce anything regarding the feasability of an approximation algorithm ?
Dju
CC BY-SA 3.0
2013-04-03T17:17:29.327Z
you can deduce that solving the LP solves the problem, so it gives an algorithm (but definitely not a linear time one)
Sasho Nikolov
CC BY-SA 3.0
2013-04-03T17:26:58.643Z
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](http://pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture02.pdf)
Sasho Nikolov
CC BY-SA 3.0
2013-04-03T21:27:37.753Z
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.
Dju
<cc.complexity-theory><approximation-algorithms><optimization><linear-programming><integrality-gap>
What does "no integrality gap" imply?
Dju
# What does "no integrality gap" imply?

(Asked by: username_0 on 2013-04-03)

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](http://www.math.uni-rostock.de/~kalinowski/papers/dual_rectangle_segmentation.pdf), 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?

**Tags:** cc.complexity-theory, approximation-algorithms, optimization, linear-programming, integrality-gap

> **Comments:**
> **username_1**: This just means that the optimal objective values of the integer program and its LP relaxation are the same.  
> **username_0**: Thank you, does this means that I cannot deduce anything regarding the feasability of an approximation algorithm ?  
> **username_2**: you can deduce that solving the LP solves the problem, so it gives an algorithm (but definitely not a linear time one)  
> **username_2**: 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](http://pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture02.pdf)  
> **username_0**: 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.  

---

## 0 answers

