Semidefinite and Lagrangian relaxations for hard combinatorial problems (Q2712834)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Semidefinite and Lagrangian relaxations for hard combinatorial problems |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Semidefinite and Lagrangian relaxations for hard combinatorial problems |
scientific article |
Statements
30 November 2002
0 references
semi-definite relaxations
0 references
combinatorial optimization
0 references
Semidefinite and Lagrangian relaxations for hard combinatorial problems (English)
0 references
This paper presents a recipe and some examples of how to find good semi-definite relaxations for combinatorial optimization problems. The main idea is to look at Lagrangian relaxations of a constrained quadratic formulation of the combinatorial optimization problem. More importantly, the paper argues by example that Lagrangian relaxation yields in some sense the best possible bounds for many problems.NEWLINENEWLINEFor the entire collection see [Zbl 0946.00028].
0 references
