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 organization: Helsinki Institute for Information Technology
Complex Systems Computation Group
Date: 2011
Language: eng
Number of pages: 26
Belongs to series: Theory of Computing Systems
ISSN: 1432-4350
DOI: https://doi.org/10.1007/s00224-010-9303-6
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
Peer reviewed: Yes
Usage restriction: openAccess
Self-archived version: acceptedVersion


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