Potential function methods for approximately solving linear programming problems: theory and practice. (Q1422252): Difference between revisions

In the present booklet the author deals with theoretical and experimental results on approximation algorithms for linear programs, with special emphasis on some potential function methods that are provably good. In Chapter 1 there are examined certain classical results on approximately solving of multicommodity flow problems providing a stepping-stone to modern research in the field of approximation algorithms. The accent is on the flow deviation method developed by \textit{L. Fratta}, \textit{M. Gerla} and \textit{L. Kleinrock} [Networks 3, 97--133 (1973)] as well as on the algorithm by \textit{F. Shahrokhi} and \textit{D. W. Matula} [J. Assoc. Comput. Mach. 37, No. 2, 318--334 (1990; Zbl 0696.68071)]. In Chapter 2 the author reviews some fundamental results on exponential potential function methods that were substantially built on and motivated by the investigations of F. Shahrokhi and D. W. Matula described in Chapter 1. He concentrates on the paper by \textit{M. D. Grigoriadis} and \textit{L. G. Khachiyan} [SIAM J. Optim. 4, 86--107 (1994; Zbl 0808.90105)] as well as on the paper by \textit{S. A. Plotkin}, \textit{D. B. Shmoys} and \textit{E. Tardos} [Math. Oper. Res. 20, No. 2, 257--301 (1995; Zbl 0837.90103)]. In Chapter 3 there are surveyed recent developments regarding approximation algorithms published by \textit{N. E. Young} [Proc. 6th ACM-SIAM Symp. on Discrete Algorithms, 170--178 (1995; Zbl 0849.90100)], \textit{M. D. Grigoriadis} and \textit{L. G. Khachiyan} [Math. Program. 75, No. 3(A), 477--482 (1996; Zbl 0874.90085)], \textit{P. Klein} and \textit{N. Young} [Proc. IPCO, 320--327 (1999; Zbl 0954.90004)], \textit{N. Garg} and \textit{J. Könemann} [Proc. 39th Ann. Symp. on Foundations of Computer Science, 300--309 (1998)], \textit{L. K. Fleischer} [SIAM J. Discrete Math. 13, No. 4, 505--520 (2000; Zbl 0968.68068)], \textit{M. Luby} and \textit{N. Nisan} [Proc. 24th Ann. ACM Symp. on Theory of Computing, 448--457 (1993)], \textit{C. Lemaréchal}, \textit{A. Nemirovskij} and \textit{Y. Nesterov} [Math. Program. 69, No. 1(B), 111--147 (1995; Zbl 0857.90102)], \textit{F. Barahova} and \textit{R. Anbil} [Math. Program. 87, No. 3(A), 385--399 (2000; Zbl 0961.90058)]. Chapter 4 contains the author's computational experiments using the exponential potential function. A general-purpose implementation of an algorithm for approximately solving block-angular linear programs is described and illustrated by applications. The author notices that he has placed special emphasis on minimizing the number of iterations, but has paid little or no attention to making the individual iterations especially fast.