Tolerant property testing and distance approximation

详细信息	查看全文 | 推荐本文 |

• 作者：Michal Parnas ; Dana Ron and Ronitt Rubinfeld
• 关键词：Property testing ; Sublinear algorithms ; Approximation ; Clustering
• 刊名：Journal of Computer and System Sciences
• 出版年：2006
• 期刊代码：186_00220000
• 类别：et
• 出版时间：September 2006
• 卷：72
• 期：6
• 页码：1012-1042
• 文件大小：431 K

摘要

In this paper we study a generalization of standard property testing where the algorithms are required to be more tolerant with respect to objects that do not have, but are close to having, the property. Specifically, a tolerant property testing algorithm is required to accept objects that are ₁-close to having a given property and reject objects that are ₂-far from having , for some parameters 0₁<₂1. Another related natural extension of standard property testing that we study, is distance approximation. Here the algorithm should output an estimate of the distance of the object to , where this estimate is sufficiently close to the true distance of the object to . We first formalize the notions of tolerant property testing and distance approximation and discuss the relationship between the two tasks, as well as their relationship to standard property testing. We then apply these new notions to the study of two problems: tolerant testing of clustering and distance approximation for monotonicity. We present and analyze algorithms whose query complexity is either polylogarithmic or independent of the size of the input.