The Lagrangian search method

MaRDI QIDQ2768049zbMATH OpenFDO

Authors Pavlos S. Efraimidis, P. G. Spirakis

Publication date 10 October 2002

zbMATH Keywords

approximate solutionLagrangian relaxationpositive linear programming

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Review text

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

Recommendations

• A technique for speeding up the solution of the Lagrangean dual
• A Lagrangean Relaxation Scheme for Structured Linear Programs With Application To Multicommodity Network Flows
• The omnipresence of Lagrange
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• scientific article; zbMATH DE number 4085396

Cited in

(2)

• scientific article; zbMATH DE number 5623945 (Why is no real title available?)
• Classroom Note: The Lagrange--Charpit Method

This page was built for publication: The Lagrangian search method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2768049)