2026-08-15T12:45:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1753 2024-03-06T10:33:04Z ddc:004 open_access

All-Norms and All-L_p-Norms Approximation Algorithms Golovin, Daniel Gupta, Anupam Kumar, Amit Tangwongsan, Kanat Approximation algorithms set-cover problems combinatorial optimization sampling minkowski norms 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 $L_p$ Set Cover problem, which generalizes \textsc{Set Cover} and \textsc{Min-Sum Set Cover}. We show that the greedy algorithm \emph{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 \emph{submodular set cover}, and prove some results for the so-called \emph{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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Golovin and Anupam Gupta and Amit Kumar and Kanat Tangwongsan 2008 Is Part Of LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2008.1753 urn:nbn:de:0030-drops-17537 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1753 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode