A note on: No need to choose: How to get both a PTAS and Sublinear Query Complexity

Nir Ailon, Zohar Karnin

We revisit various PTAS's (Polynomial Time Approximation Schemes) for minimization versions of dense problems, and show that they can be performed with sublinear query complexity.…