Local approximability of max-min and min-max linear programs
Contribuinte(s) |
University of Helsinki, Department of Computer Science University of Helsinki, Department of Computer Science (-2009) University of Helsinki, Helsinki Institute for Information Technology HIIT (-2009) University of Helsinki, Helsinki Institute for Information Technology HIIT University of Helsinki, Helsinki Institute for Information Technology HIIT |
---|---|
Data(s) |
2011
|
Resumo |
In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0. In a min-max LP, the objective is to minimise ρ subject to Ax ≤ ρ1, Cx ≥ 1, and x ≥ 0. The matrices A and C are nonnegative and sparse: each row ai of A has at most ΔI positive elements, and each row ck of C has at most ΔK positive elements. We study the approximability of max-min LPs and min-max LPs in a distributed setting; in particular, we focus on local algorithms (constant-time distributed algorithms). We show that for any ΔI ≥ 2, ΔK ≥ 2, and ε > 0 there exists a local algorithm that achieves the approximation ratio ΔI (1 − 1/ΔK) + ε. We also show that this result is the best possible: no local algorithm can achieve the approximation ratio ΔI (1 − 1/ΔK) for any ΔI ≥ 2 and ΔK ≥ 2. |
Formato |
26 |
Identificador |
http://hdl.handle.net/10138/28034 1432-4350 |
Idioma(s) |
eng |
Publicador |
SPRINGER NEW YORK LLC |
Relação |
Theory of Computing Systems |
Direitos |
The final publication is available at www.springerlink.com. |
Fonte |
Floréen , P , Hassinen , M , Kaasinen , J , Kaski , P , Musto , T & Suomela , J 2011 , ' Local approximability of max-min and min-max linear programs ' Theory of Computing Systems , vol 49 , no. 4 , pp. 672–697 . , 10.1007/s00224-010-9303-6 |
Palavras-Chave | #113 Computer and information sciences |
Tipo |
A1 Refereed journal article info:eu-repo/semantics/article info:eu-repo/semantics/acceptedVersion |