Paper Info
Title
A note on: No need to choose: How to get both a PTAS and Sublinear Query Complexity
Abstract
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. This means that not only do we obtain a (1+eps)-approximation to the NP-Hard problems in polynomial time, but also avoid reading the entire input. This setting is particularly advantageous when the price of reading parts of the input is high, as is the case, for examples, where humans provide the input. Trading off query complexity with approximation is the raison d'etre of the field of learning theory, and of the ERM (Empirical Risk Minimization) setting in particular. A typical ERM result, however, does not deal with computational complexity. We discuss two particular problems for which (a) it has already been shown that sublinear querying is sufficient for obtaining a (1 + eps)-approximation using unlimited computational power (an ERM result), and (b) with full access to input, we could get a (1+eps)-approximation in polynomial time (a PTAS). Here we show that neither benefit need be sacrificed. We get a PTAS with efficient query complexity.
Year
Venue
Field
2012
CoRR
Sublinear function,Discrete mathematics,Mathematical optimization,Empirical risk minimization,Minification,Time complexity,Mathematics,Computational complexity theory
DocType
Volume
Citations 
Journal
abs/1204.6588
2
PageRank 
References 
Authors
0.37
3
2
Name
Order
Citations
PageRank
Nir Ailon1111470.74
Zohar S. Karnin226620.98