We consider approximation algorithms for covering integer programs of the
form min $\langle c, x \rangle $ over $x \in \mathbb{N}^n $ subject to $A x
\geq b $ and $x \leq d$; where $A \in \mathbb{R}_{\geq 0}^{m \times n}$, $b \in
\mathbb{R}_{\geq 0}^m$, and $c, d \in \mathbb{R}_{\geq 0}^n$ all have
nonnegative entries. We refer to this problem as $\operatorname{CIP}$, and the
special case without the multiplicity constraints $x \le d$ as
$\operatorname{CIP}_{\infty}$. These problems generalize the well-studied Set
Cover problem. We make two algorithmic contributions.
First, we show that a simple algorithm based on randomized rounding with
alteration improves or matches the best known approximation algorithms for
$\operatorname{CIP}$ and $\operatorname{CIP}_{\infty}$ in a wide range of
parameter settings, and these bounds are essentially optimal. As a byproduct of
the simplicity of the alteration algorithm and analysis, we can derandomize the
algorithm without any loss in the approximation guarantee or efficiency.
Previous work by Chen, Harris and Srinivasan [12] which obtained near-tight
bounds is based on a resampling-based randomized algorithm whose analysis is
complex.
Non-trivial approximation algorithms for $\operatorname{CIP}$ are based on
solving the natural LP relaxation strengthened with knapsack cover (KC)
inequalities [5,24,12]. Our second contribution is a fast (essentially
near-linear time) approximation scheme for solving the strengthened LP with a
factor of $n$ speed up over the previous best running time [5].
Together, our contributions lead to near-optimal (deterministic)
approximation bounds with near-linear running times for $\operatorname{CIP}$
and $\operatorname{CIP}_{\infty}$.

本文针对覆盖整数规划问题提出了基于随机取整与修改的简单算法来改进其逼近度，并证明了近似度几乎是最优的，并且在没有失去逼近保证或效率的情况下可以去随机化，同时也提出了一种基于强化的线性规划近似方案，其运行时间比之前的最优解快 n 倍。这两个算法的组合使得本文提出的覆盖整数规划问题算法在近乎线性的时间内得到准确的结果。