Hitting sets when the VC-dimension is small

被引：73

作者：

Even, G ^{[1
]}

Rawitz, D ^{[1
]}

Shahar, S ^{[1
]}

机构：

[1] Tel Aviv Univ, Sch Elect Engn, Tel Aviv, Israel

来源：

INFORMATION PROCESSING LETTERS | 2005年 / 95卷 / 02期

关键词：

approximation algorithms; computational geometry; hitting set; VC-dimension;

D O I：

10.1016/j.ipl.2005.03.010

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present an approximation algorithm for the hitting set problem when the VC-dimension of the set system is small. Our algorithm uses a linear programming relaxation to compute a probability measure for which epsilon-nets are always hitting sets (see Corollary 15.6 in Pach and Agarwal [Combinatorial Geometry, J. Wiley, New York, 1995]). The comparable algorithm of Bronnimann and Goodrich [Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom. 14 (1995) 463] computes such a probability measure by an iterative reweighting technique. The running time of our algorithm is comparable with theirs, and the approximation ratio is smaller by a constant factor. We also show how our algorithm can be parallelized and extended to the minimum cost hitting set problem. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：358 / 362

页数：5

共 12 条

[1] LEARNABILITY AND THE VAPNIK-CHERVONENKIS DIMENSION [J].