  $ \newcommand{\Re}{\mathbb{R}} \newcommand{\BX}{\mathcal{B}}
\newcommand{\bb}{\mathsf{b}} \newcommand{\eps}{\varepsilon}
\newcommand{\polylog}{\mathrm{polylog}} $
  Let $\BX=\{\bb_1, \ldots ,\bb_n\}$ be a set of $n$ axis-aligned boxes in
$\Re^d$ where $d\geq2$ is a constant. The piercing problem is to compute a
smallest set of points $N \subset \Re^d$ that hits every box in $\BX$, i.e.,
$N\cap \bb_i\neq \emptyset$, for $i=1,\ldots, n$. The problem is known to be
NP-Hard. Let $\psi:=\psi(\BX)$, the \emph{piercing number} be the minimum size
of a piercing set of $\BX$. We first present a randomized $O(\log\log
\psi)$-approximation algorithm with expected running time $O(n^{d/2}\polylog
(n))$. Next, we show that the expected running time can be improved to
near-linear using a sampling-based technique, if $\psi = O(n^{1/(d-1)})$.
Specifically, in the plane, the improved running time is $O(n \log \psi)$,
assuming $\psi < n/\log^{\Omega(1)} n$. Finally, we study the dynamic version
of the piercing problem where boxes can be inserted or deleted. For boxes in
$\Re^2$, we obtain a randomized $O(\log\log\psi)$-approximation algorithm with
$O(n^{1/2}\polylog (n))$ amortized expected update time for insertion or
deletion of boxes. For squares in $\Re^2$, the update time can be improved to
$O(n^{1/3}\polylog (n))$.
  Our algorithms are based on the multiplicative weight-update (MWU) method and
require the construction of a weak $\eps$-net for a point set with respect to
boxes. A key idea of our work is to exploit the duality between the piercing
set and independent set (for boxes) to speed up our MWU. We also present a
simpler and slightly more efficient algorithm for constructing a weak
$\eps$-net than in [Ezr10], which is of independent interest. Our approach also
yields a simpler algorithm for constructing (regular) $\eps$-nets with respect
to boxes for $d=2,3$.
