10.4230/LIPICS.FSTTCS.2008.1753
Golovin, Daniel
Daniel
Golovin
Gupta, Anupam
Anupam
Gupta
Kumar, Amit
Amit
Kumar
Tangwongsan, Kanat
Kanat
Tangwongsan
All-Norms and All-L_p-Norms Approximation Algorithms
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
Approximation algorithms
set-cover problems
combinatorial optimization
sampling minkowski norms
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
2008
2008-12-05
2008-12-05
2008-12-05
en
urn:nbn:de:0030-drops-17537
10.4230/LIPIcs.FSTTCS.2008
978-3-939897-08-8
1868-8969
10.4230/LIPIcs.FSTTCS.2008
LIPIcs, Volume 2, FSTTCS 2008
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
2
10
199
210
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
2
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
465095 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 199-210