All-norms and all-Lp-norms approximation algorithms

Daniel Golovin, Anupam Gupta, Amit Kumar, Kanat Tangwongsan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 Lp-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 Lp 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-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.

Original languageEnglish (US)
Title of host publicationFSTTCS 2008 - IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Pages199-210
Number of pages12
StatePublished - 2008
Event28th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008 - Bangalore, India
Duration: Dec 9 2008Dec 11 2008

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume2
ISSN (Print)1868-8969

Conference

Conference28th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008
Country/TerritoryIndia
CityBangalore
Period12/9/0812/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-Lp-norms approximation algorithms'. Together they form a unique fingerprint.

Cite this