## 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 could obtain a solution that optimizes 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 in this framework is the Lp Set Cover problem, which generalizes SET COVER and MIN-SUM SET COVER. We show that the greedy algorithm simultaneously gives a (p + ln p + O(1))-approximation for all p, and show that this approximation ratio is optimal up to constants under reasonable complexity-theoretic assumptions. We additionally 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-L_{p}-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.

Original language | English (US) |
---|---|

Title of host publication | FSTTCS 2008 - IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |

Pages | 199-210 |

Number of pages | 12 |

State | Published - 2008 |

Event | 28th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008 - Bangalore, India Duration: Dec 9 2008 → Dec 11 2008 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 2 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 28th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008 |
---|---|

Country/Territory | India |

City | Bangalore |

Period | 12/9/08 → 12/11/08 |

## Keywords

- Approximation algorithms
- Combinatorial optimization
- Sampling minkowski norms
- Set-cover problems

## ASJC Scopus subject areas

- Software

## Fingerprint

Dive into the research topics of 'All-norms and all-L_{p}-norms approximation algorithms'. Together they form a unique fingerprint.