Local approximability of max-min and min-max linear programs

Visa fullständig post



Permalänk

http://hdl.handle.net/10138/28034

Citation

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 . https://doi.org/10.1007/s00224-010-9303-6

Titel: Local approximability of max-min and min-max linear programs
Författare: Floréen, Patrik; Hassinen, Marja; Kaasinen, Joel; Kaski, Petteri; Musto, Topi; Suomela, Jukka
Upphovmannens organisation: Helsinki Institute for Information Technology
Complex Systems Computation Group
Datum: 2011
Språk: eng
Sidantal: 26
Tillhör serie: Theory of Computing Systems
ISSN: 1432-4350
DOI: https://doi.org/10.1007/s00224-010-9303-6
Permanenta länken (URI): http://hdl.handle.net/10138/28034
Abstrakt: 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.
Subject: 113 Computer and information sciences
Referentgranskad: Ja
Användningsbegränsning: openAccess
Parallelpublicerad version: acceptedVersion


Filer under denna titel

Totalt antal nerladdningar: Laddar...

Filer Storlek Format Granska
floreen_2011_max_min_lp.pdf 340.3Kb PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post