TY - GEN
T1 - All-norms and all-Lp-norms approximation algorithms
AU - Golovin, Daniel
AU - Gupta, Anupam
AU - Kumar, Amit
AU - Tangwongsan, Kanat
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - Combinatorial optimization
KW - Sampling minkowski norms
KW - Set-cover problems
UR - http://www.scopus.com/inward/record.url?scp=84880213713&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84880213713&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84880213713
SN - 9783939897088
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 199
EP - 210
BT - FSTTCS 2008 - IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
T2 - 28th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008
Y2 - 9 December 2008 through 11 December 2008
ER -