  We study the generalized min sum set cover (GMSSC) problem, wherein given a
collection of hyperedges $E$ with arbitrary covering requirements $k_e$, the
goal is to find an ordering of the vertices to minimize the total cover time of
the hyperedges; a hyperedge $e$ is considered covered by the first time when
$k_e$ many of its vertices appear in the ordering. We give a $4.642$
approximation algorithm for GMSSC, coming close to the best possible bound of
$4$, already for the classical special case (with all $k_e=1$) of min sum set
cover (MSSC) studied by Feige, Lov\'{a}sz and Tetali, and improving upon the
previous best known bound of $12.4$ due to Im, Sviridenko and van der Zwaan.
Our algorithm is based on transforming the LP solution by a suitable kernel and
applying randomized rounding. This also gives an LP-based $4$ approximation for
MSSC. As part of the analysis of our algorithm, we also derive an inequality on
the lower tail of a sum of independent Bernoulli random variables, which might
be of independent interest and broader utility.
  Another well-known special case is the min sum vertex cover (MSVC) problem,
in which the input hypergraph is a graph and $k_e = 1$, for every edge. We give
a $16/9$ approximation for MSVC, and show a matching integrality gap for the
natural LP relaxation. This improves upon the previous best $1.999946$
approximation of Barenholz, Feige and Peleg. (The claimed $1.79$ approximation
result of Iwata, Tetali and Tripathi for the MSVC turned out have an
unfortunate, seemingly unfixable, mistake in it.) Finally, we revisit MSSC and
consider the $\ell_p$ norm of cover-time of the hyperedges. Using a dual
fitting argument, we show that the natural greedy algorithm achieves tight, up
to NP-hardness, approximation guarantees of $(p+1)^{1+1/p}$, for all $p\ge 1$.
For $p=1$, this gives yet another proof of the $4$ approximation for MSSC.
