The 2-quasi-greedy algorithm for cardinality constrained matroid bases (Q1079134)
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 3961373
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The 2-quasi-greedy algorithm for cardinality constrained matroid bases |
scientific article; zbMATH DE number 3961373 |
Statements
The 2-quasi-greedy algorithm for cardinality constrained matroid bases (English)
0 references
1986
0 references
The quasi-greedy algorithm is generalized to provide an efficient 2- quasi-greedy algorithm for a minimum weight base constrained to have a fixed number of elements from two disjoint sets. It is shown that optimal bases for adjacent states may not themselves be adjacent, however, optimal solutions for adjacent states can be found from information about the current base. Moreover, a further increase of efficiency is shown to be possible by jumping over certain adjacent states.
0 references
quasi-greedy algorithm
0 references
minimum weight base
0 references
0.7771145701408386
0 references
0.7768688797950745
0 references
0.7747756838798523
0 references
0.7745485901832581
0 references
