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

Show simple item record

dc.contributor.author Floréen, Patrik
dc.contributor.author Hassinen, Marja
dc.contributor.author Kaasinen, Joel
dc.contributor.author Kaski, Petteri
dc.contributor.author Musto, Topi
dc.contributor.author Suomela, Jukka
dc.date.accessioned 2011-10-24T13:40:02Z
dc.date.available 2011-10-24T13:40:02Z
dc.date.issued 2011
dc.identifier.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
dc.identifier.other PURE: 19027858
dc.identifier.other PURE UUID: 760a0034-6de6-4098-bf16-f4c151830d36
dc.identifier.other WOS: 000295519200002
dc.identifier.other Scopus: 80053443789
dc.identifier.other ORCID: /0000-0001-7347-0685/work/32017454
dc.identifier.uri http://hdl.handle.net/10138/28034
dc.description.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. en
dc.format.extent 26
dc.language.iso eng
dc.relation.ispartof Theory of Computing Systems
dc.rights.uri info:eu-repo/semantics/openAccess
dc.subject 113 Computer and information sciences
dc.title Local approximability of max-min and min-max linear programs en
dc.type Article
dc.contributor.organization Helsinki Institute for Information Technology
dc.contributor.organization Complex Systems Computation Group
dc.description.reviewstatus Peer reviewed
dc.relation.doi https://doi.org/10.1007/s00224-010-9303-6
dc.relation.issn 1432-4350
dc.rights.accesslevel openAccess
dc.type.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 simple item record