maxWeightBasis -- maximum weight basis using greedy algorithm

Synopsis

• Usage:
maxWeightBasis(M, w)
• Inputs:
• M,
• w, a list, a weight function
• Outputs:
• a set, a maximum-weight basis obtained by the greedy algorithm

Description

For a matroid M on ground set E, a weight function on M is a function $w : E -> \mathbb{R}$, extended to all subsets of E by setting $w(X) := \sum_{x\in X} w(x)$. The greedy algorithm for finding a maximum-weight independent subset of E starts with the empty set, and proceeds by successively adding elements of E of maximum weight, which together with the elements already added, form an independent set.

In this method, a weight function is specified by its list of values on E. Thus if $E = \{e_1, ..., e_n\}$, then w is represented as the list $\{w(e_1), ..., w(e_n)\}$.

Matroids can be characterized via the greedy algorithm as follows: a set $\mathcal{I}$ of subsets of E is the set of independent sets of a matroid on E iff $\mathcal{I}$ is nonempty, downward closed, and for every weight function $w : E -> \mathbb{R}$, the greedy algorithm returns a maximal member of $\mathcal{I}$ of maximum weight.

 i1 : M = matroid completeGraph 4 o1 = a matroid of rank 3 on 6 elements o1 : Matroid i2 : bases M o2 = {set {2, 4, 5}, set {1, 4, 5}, set {0, 4, 5}, set {2, 3, 5}, set {1, 3, ------------------------------------------------------------------------ 5}, set {0, 3, 5}, set {0, 2, 5}, set {0, 1, 5}, set {2, 3, 4}, set {1, ------------------------------------------------------------------------ 3, 4}, set {0, 3, 4}, set {1, 2, 4}, set {0, 1, 4}, set {1, 2, 3}, set ------------------------------------------------------------------------ {0, 2, 3}, set {0, 1, 2}} o2 : List i3 : w1 = apply(M_*, e -> (toList e)#1) o3 = {1, 2, 3, 2, 3, 3} o3 : List i4 : maxWeightBasis(M, w1) o4 = set {2, 4, 5} o4 : Set i5 : w2 = rsort w1 o5 = {3, 3, 3, 2, 2, 1} o5 : List i6 : maxWeightBasis(M, w2) o6 = set {0, 1, 2} o6 : Set

Ways to use maxWeightBasis :

• "maxWeightBasis(Matroid,List)"

For the programmer

The object maxWeightBasis is .