https://discopal.ispras.ru/index.php?action=history&feed=atom&title=En.plpapx.htm 2026-05-09T12:13:15Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=En.plpapx.htm&diff=607&oldid=prev 2010-11-25T20:03:44Z

<p>Новая страница: «== A Fast and Simple Approximation Algorithm for Positive Linear Programming == We introduce a new fast parallel approximation algorithm for Positive Linear Program...»</p> <p><b>Новая страница</b></p><div>== A Fast and Simple Approximation Algorithm for Positive Linear Programming ==<br /> <br /> 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 &lt;tt&gt;[LN93]&lt;/tt&gt;, &lt;tt&gt;[BBR97]&lt;/tt&gt;, 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 &lt;m&gt;O(\frac{mn}{\varepsilon^2}\log^2\frac{mn}{\varepsilon})&lt;/m&gt;, which is the new best upper bound.<br /> <br /> The parallel complexity of the algorithm is &lt;m&gt;O(\frac{1}{\varepsilon^4}\log^4\frac{mn}{\varepsilon})&lt;/m&gt;, which is close to the best known bounds.<br /> <br /> Our computational experiments show an advantage of our algorithm in the running time over the algorithms in &lt;tt&gt;[GK98]&lt;/tt&gt;, &lt;tt&gt;[BBR97]&lt;/tt&gt; on random input matrices.<br /> <br /> === Publication ===<br /> <br /> S.A.Fomin, [http://discopal.ispras.ru/papers/plpapx_conf2000.ps A Fast and Simple Approximation Algorithm for Positive Linear Programming]. (English version of &quot;Novyjj priblizhennyjj algoritm dlja zadachi polozhitel`nogo linejjnogo programmirovanija&quot; Diskretnyjj analiz i issledovanie operacijj. Serija 2. Tom 8. N.2.).<br /> <br /> == References == <br /> ;[BBR97]: Yair Bartal, John W. Byers, Danny Raz, Global Optimization Using Local Information with Application to Flow Control, IEEE FOCS 97, 1997, 303-311.<br /> <br /> ;[GK98]: N. Garg, J. Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems, FOCS 98 300-309.<br /> <br /> ;[LN93]: M. Luby and N. Nisan, A Parallel Approximation Algorithm for Positive Linear Programming, Proc. of 25th ACM STOC, 448-457, 1993.<br /> <br /> ;[PST92]: Plotkin S., Shmoys D., Tardos E., Fast Approximation Algorithms for Fractional Packing and Covering Problems, Proc. 32nd IEEE FOCS 91, 1991, 495-504.</div>

StasFomin