Before revision:  We first present a simple algorithm that makes O(r/\epsilon^3) queries and approximates the LIS  with an additive error bounded by \epsilon n.
After revision:  We first present a simple algorithm that makes O(r/\epsilon^3) queries and approximates the LIS length with an additive error bounded by \epsilon n.