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 could obtain a solution that optimized several norms simultaneously.

In this paper, we examine approximation algorithms that simultaneously perform well on all norms, or on all L_p norms. A natural problem to consider in this framework is the set-cover problem: suppose we pick sets S₁, S₂, . . . , S_t (in that order), and define the cover time of element e to be Ce = min{i | e 2 Si}, the index of the first set that covers e. Minimizing the maximum cover time kCk1 gives us the classical MIN SET COVER, for which the greedy algorithm is an O(log n) approximation (which is best possible). Minimizing the average (or total) cover time Pe Ce = kCk1 gives the MIN-SUM SET COVER 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 kCkp = (Pe Cpe )1/p for 1 p 1?

We give tight results for this problem: the greedy algorithm simultaneously gives an O(p)-approximation for Lp-Set-Cover for all values of 1 p < 1 (even for the weighted version). 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 Ω(p) under suitable complexity assumptions. We show how to use our analysis techniques to give similar results for the more general submodular set cover, and prove some results for the so-called pipelined set cover problem.

We then go on to examine approximation algorithms in the "all-norms" and the "all-Lp-norms" frameworks more broadly, and present algorithms and structural results for other problems such as k-facility-location, TSP, and average flow-time minimization, extending and unifying previously known results.

22 pages

*Department of Computer Science & Engineering, Indian Institute of Technology, Hauz Khas, New Dehhi, India - 110016

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu