Efficient construction of a small hitting set for combinatorial rectangles in high dimension
- 1 January 1993
- proceedings article
- Published by Association for Computing Machinery (ACM)
- Vol. 17 (2) , 258-267
- https://doi.org/10.1145/167088.167166
Abstract
Given d, m and ffl, we deterministically producea sequence of points S that hits every combinatorialrectangle in [m]dof volume at least ffl.Both the running time of the algorithm and jSjare polynomial in m log(d)=ffl. This algorithmhas applications to deterministic constructionsof small sample spaces for general multivaluedrandom variables.1 IntroductionThe problem we consider in this paper is motivatedby the following basic witness findingproblem: design an efficient algorithm ...This publication has 0 references indexed in Scilit: