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

Show full item record



Permalink

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

Title: Local approximability of max-min and min-max linear programs
Author: Floréen, Patrik; Hassinen, Marja; Kaasinen, Joel; Kaski, Petteri; Musto, Topi; Suomela, Jukka
Contributor: University of Helsinki, Helsinki Institute for Information Technology
University of Helsinki, Helsinki Institute for Information Technology
University of Helsinki, Helsinki Institute for Information Technology
University of Helsinki, Helsinki Institute for Information Technology
University of Helsinki, Helsinki Institute for Information Technology
Date: 2011
Language: eng
Number of pages: 26
Belongs to series: Theory of Computing Systems
ISSN: 1432-4350
URI: http://hdl.handle.net/10138/28034
Abstract: 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
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
floreen_2011_max_min_lp.pdf 340.3Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record