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 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.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.