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

Näytä kaikki kuvailutiedot



Pysyväisosoite

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

Lähdeviite

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

Julkaisun nimi: Local approximability of max-min and min-max linear programs
Tekijä: Floréen, Patrik; Hassinen, Marja; Kaasinen, Joel; Kaski, Petteri; Musto, Topi; Suomela, Jukka
Tekijän organisaatio: Helsinki Institute for Information Technology
Complex Systems Computation Group
Päiväys: 2011
Kieli: eng
Sivumäärä: 26
Kuuluu julkaisusarjaan: Theory of Computing Systems
ISSN: 1432-4350
DOI-tunniste: https://doi.org/10.1007/s00224-010-9303-6
URI: http://hdl.handle.net/10138/28034
Tiivistelmä: 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.
Avainsanat: 113 Computer and information sciences
Vertaisarvioitu: Kyllä
Pääsyrajoitteet: openAccess
Rinnakkaistallennettu versio: acceptedVersion


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
floreen_2011_max_min_lp.pdf 340.3KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot