# En.plpapx.htm

Перейти к: навигация, поиск
== 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 <tt>[LN93]</tt>, <tt>[BBR97]</tt>, 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 <m>O(\frac{mn}{\varepsilon^2}\log^2\frac{mn}{\varepsilon})</m>, which is the new best upper bound.

The parallel complexity of the algorithm is <m>O(\frac{1}{\varepsilon^4}\log^4\frac{mn}{\varepsilon})</m>, 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 <tt>[GK98]</tt>, <tt>[BBR97]</tt> on random input matrices.

=== Publication ===

S.A.Fomin, [http://discopal.ispras.ru/papers/plpapx_conf2000.ps A Fast and Simple Approximation Algorithm for Positive Linear Programming]. (English version of "Novyjj priblizhennyjj algoritm dlja zadachi polozhitelnogo 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.`
Источник — «http://discopal.ispras.ru/En.plpapx.htm»