The Lagrangian search method (Q2768049)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1698942
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The Lagrangian search method |
scientific article; zbMATH DE number 1698942 |
Statements
10 October 2002
0 references
Lagrangian relaxation
0 references
positive linear programming
0 references
approximate solution
0 references
The Lagrangian search method (English)
0 references
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].
0 references
0.7766720652580261
0 references
0.7766720652580261
0 references
0.7714480757713318
0 references
0.7711923122406006
0 references
