Efficient construction of a small hitting set for combinatorial rectangles in high dimension (Q1382408)

A rectangle is a subset of \([m]^d=\{1,2,3,\dots,m\}^d\) of form \(R_1\times R_2\times \dots\times R_d\). Its volume is \((\Pi |R_i|)/m^d\). A deterministic algorithm is given which, on input integers \(d\), \(m\) and a real number \(\varepsilon\in (0,1)\) produces a subset of \([m]^d\) that hits every rectangle of volume at least \(\varepsilon\). The time is a polynomial in \(md/\varepsilon\) and the size of the subset is a polynomial in \(m(\log d)/\varepsilon\).