Local Approximability of Max-Min and Min-Max Linear Programs
Local Approximability of Max-Min and Min-Max Linear Programs
复制标题
最大-最小和最小-最大线性规划的局部逼近性
DOI：
--
复制
发表时间：
2011
影响因子：
0.5
通讯作者：
J. Suomela
中科院分区：
文献类型：
--
作者：
P. Floréen;Marja Hassinen;Joel Kaasinen;P. Kaski;Topi Musto;J. Suomela
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.
