En.plpapx.htm — различия между версиями

Текущая версия на 20:03, 25 ноября 2010

A Fast and Simple Approximation Algorithm for Positive Linear Programming

We introduce a new fast parallel approximation algorithm for Positive Linear Programming (PLP), i.e. a special case of Linear Programming in packing/covering form, when the input constraint matrix and the constraint vector consists entirely of nonnegative entries. Our algorithm, which draws from techniques developed in [LN93], [BBR97], is simpler than the previous approximation algorithms for positive linear programs and has efficient parallel and sequential implementations. In particular, the time complexity of sequential implementation is , which is the new best upper bound.

The parallel complexity of the algorithm is , which is close to the best known bounds.

Our computational experiments show an advantage of our algorithm in the running time over the algorithms in [GK98], [BBR97] on random input matrices.

Publication

S.A.Fomin, A Fast and Simple Approximation Algorithm for Positive Linear Programming. (English version of "Novyjj priblizhennyjj algoritm dlja zadachi polozhitel`nogo linejjnogo programmirovanija" Diskretnyjj analiz i issledovanie operacijj. Serija 2. Tom 8. N.2.).

References

[BBR97]

Yair Bartal, John W. Byers, Danny Raz, Global Optimization Using Local Information with Application to Flow Control, IEEE FOCS 97, 1997, 303-311.

[GK98]

N. Garg, J. Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems, FOCS 98 300-309.

[LN93]

M. Luby and N. Nisan, A Parallel Approximation Algorithm for Positive Linear Programming, Proc. of 25th ACM STOC, 448-457, 1993.

[PST92]

Plotkin S., Shmoys D., Tardos E., Fast Approximation Algorithms for Fractional Packing and Covering Problems, Proc. 32nd IEEE FOCS 91, 1991, 495-504.