The Lagrangian search method (Q2768049)

The authors present techniques to derive algorithms for combinatorial optimisation problems that can be modelled as extensions of positive linear programs. This work is based on results for fractional covering and packing problems. A Lagrangian search method is developed to deal with the extensions. It is shown that for poly-bottleneck problems a relaxed approximation solution is found in \(O(\operatorname {polylog} n/\varepsilon)\) steps. The problem of global routing in gate arrays is presented as an example. Other examples are mentioned.NEWLINENEWLINEFor the entire collection see [Zbl 0968.00020].