Kanat Tangongsan

L_p-Norm Set Cover

Abstract:

In many optimization problems, a solution can be viewed as ascribing a
``cost'' to each client, and the goal is to optimize some aggregation of
the per-client costs. We often optimize some $L_p$-norm (or some other
symmetric convex function or norm) of the vector of costs---though
different applications may suggest different norms to use. Ideally, we
want to obtain a solution that optimizes several norms simultaneously.

We will examine a natural problem in this framework: the $L_p$ set-cover
problem. Suppose we pick sets $S_1, S_2, ldots, S_t$ (in that order),
and define the {em cover time} of an element $e$ to be $C_e = \min{i | e
in S_i}$, the index of the first set that covers $e$. Minimizing the
maximum cover time $|C|_infty$ gives us the classical  min-set cover,
for which the greedy algorithm is an $O(log n)$ approximation (which is
the best possible). Minimizing the average (or total) cover time $\sum_e
C_e = |C|_1$ gives the min-sum set-cover (mssc) problem, for which the
greedy algorithm gives a 4-approximation (which also is tight). This
leads us to a natural question:

   How well does the greedy algorithm perform for the $L_p$ set-cover
problem, where the objective function is
   $|C|_p = (\sum_e C_e^p)^{1/p}$ for $1 \leq p \leq \infty$?

In this talk, we will give tight results for this problem: the greedy
algorithm  \emph{simultaneously} gives an $O(p)$-approximation for
$L_p$-Set-Cover for all values of $1 leq p < infty$ (even for the
weighted version), and that there are simple examples where this is
tight for all values of $p$. In fact, we also show that for every fixed
value of $p$, no efficient algorithm can obtain an approximation
guarantee better than $\Omega(p)$ under suitable complexity assumptions.
We will show how to apply our analysis techniques to the more general
{\em submodular set cover} and prove some results for the so-called {\em
pipelined set cover} problem.

This is joint work with Daniel Golovin, Anupam Gupta, and Amit Kumar.