Strong LP duality in weighted infinite bipartite graphs (Q1332441)
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 626359
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Strong LP duality in weighted infinite bipartite graphs |
scientific article; zbMATH DE number 626359 |
Statements
Strong LP duality in weighted infinite bipartite graphs (English)
0 references
29 August 1994
0 references
The problems of fractional maximum weight matching and the corresponding minimum cover are considered for bipartite graphs. It is well known that for finite graphs and integer weights the max = min relation can be attained for integer solutions. Here the question is studied for infinite graphs via the complementary slackness conditions.
0 references
linear programming duality
0 references
LP duality
0 references
fractional maximum weight matching
0 references
minimum cover
0 references
bipartite graphs
0 references
complementary slackness conditions
0 references
0.845621645450592
0 references
0.8180699944496155
0 references
0.8114473223686218
0 references
0.8040499687194824
0 references
0.7916004061698914
0 references
