2011 LocalApproximabilityofMaxMinand

• (Floréen et al., 2011) ⇒ Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, and Jukka Suomela. (2011). “Local Approximability of Max-Min and Min-Max Linear Programs.” In: Theory of Computing Systems Journal, 49(4). doi:10.1007/s00224-010-9303-6

Subject Headings: Max-Min Linear Program.

Cited By

• http://scholar.google.com/scholar?q=%22Local+Approximability+of+Max-Min+and+Min-Max+Linear+Programs%22+2011
• http://dl.acm.org/citation.cfm?id=2110337.2110338&preflayout=flat#citedby

Quotes

Author Keywords

• Distributed algorithms; Linear programs; Local algorithms

Abstract

In a max-min LP, the objective is to maximise ω subject to A x≤1, C x≥ω 1, and x≥0. In a min-max LP, the objective is to minimise ρ subject to A x≤ρ 1, C x≥1, and x≥0. The matrices A and C are nonnegative and sparse: each row a _i of A has at most Δ_I positive elements, and each row c _k 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.

1. Introduction

In a max-min linear program (max-min LP), the objective is to (1)

maximise [math]\displaystyle{ w }[/math]

subject to [math]\displaystyle{ A\bf{x} \le 1; C\bf{x} \ge \lt math\gt w }[/math] 1; \bf{x} \ge 0.</math>

A min-max linear program (min-max LP) is analogous: the objective is to (2)

minimise [math]\displaystyle{ p }[/math]

subject to [math]\displaystyle{ A\bf{x} \le p 1; C\bf{x} \ge 1; \bf{x} \ge 0. }[/math]

In both cases, A and C are nonnegative matrices.

In this work, we study max-min LPs and min-max LPs in a distributed setting. We present a local algorithm (constant-time distributed algorithm) for approximating these LPs, and we show that the approximation factor of our algorithm is the best possible among all local algorithms.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 LocalApproximabilityofMaxMinand	Petteri Kaski Patrik Floréen Marja Hassinen Joel Kaasinen Topi Musto Jukka Suomela			Local Approximability of Max-Min and Min-Max Linear Programs				10.1007/s00224-010-9303-6