The greedy algorithm on an independence system

Sort by weight, take what keeps independence. Only positive weights are taken, since a negative element can never improve a maximum-weight independent set.

Usage

morie_greedy_independent_set(ground, independent, weights)

Arguments

ground, independent

The system.

weights

Numeric vector aligned with ground.

Value

A list with set and weight.

References

Edmonds J (1971) Math Prog 1:127-136.

Examples

morie_greedy_independent_set(ground = c(1, 2, 3, 4, 5, 6, 7, 8),
  independent = c(1, 2, 3, 4, 5, 6, 7, 8), weights = c(1, 2, 3, 4, 5, 6, 7, 8))
#> $set
#> [1] 8
#> 
#> $weight
#> [1] 8
#>