TY -
T1 - Local approximability of max-min and min-max linear programs
SN - /
UR - http://hdl.handle.net/10138/28034
T3 -
A1 - Floréen, Patrik; Hassinen, Marja; Kaasinen, Joel; Kaski, Petteri; Musto, Topi; Suomela, Jukka
A2 -
PB -
Y1 - 2011
LA - eng
AB - 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). W...
VO -
IS -
SP -
OP -
KW - 113 Computer and information sciences
N1 -
PP -
ER -