Weighted Matroid Article Index for
Weighted 		 

Information About

Weighted Matroid
  CATEGORIES ABOUT WEIGHTED MATROID
   
matroid theory
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



In Combinatorics , a branch of Mathematics , a weighted matroid is a Matroid endowed with function with respect to which one can perform a greedy algorithm.

There is a simple algorithm for finding a basis:

  • Let A be the empty set.

  • For each ''x'' in ''E''

  • --- if A U {x} is independent, then set A to A U {x}.


The result is clearly an independent set. It is a maximal independent set because if B U {x} is not independent for some subset B of A, then A U {x} is not independent either (the contrapositive follows from the hereditary property). Thus if we pass up an element, we'll never have an opportunity to use it later. We will generalize this algorithm to solve a harder problem.

A ''weight function'' ''w'' : ''E'' → R+ for a matroid ''M''=(''E'', ''I'') assigns a strictly positive weight to each element of ''E''. We extend the function to subsets of ''E'' by summation; ''w''(''A'') is the sum of ''w''(''x'') over ''x'' in ''A''. A matroid with an associated weight function is called a weighted matroid.

As a simple example, say we wish to find the Maximum Spanning Forest of a graph. That is, given a graph and a weight for each edge, find a forest containing every vertex and maximizing the total weight of the edges in the tree. This problem arises in some clustering applications. If we look at the definition of the forest matroid above, we see that the maximum spanning forest is simply the independent set with largest total weight — such a set must span the graph, for otherwise we can add edges without creating cycles. But how do we find it?

An independent set of largest total weight is called an ''optimal'' set. Optimal sets are always bases, because if an edge can be added, it should be; this only increases the total weight. As it turns out, there is a trivial Greedy Algorithm for computing an optimal set of a weighted matroid. It works as follows:

  • Let A be the empty set.

  • For each ''x'' in ''E'', taken in (monotonically) decreasing order by weight

  • --- if A U {x} is independent, then set A to A U {x}.


This algorithm finds a basis, since it is a special case of the above algorithm. It always chooses the element of largest weight that it can while preserving independence (thus the term "greedy"). This always produces an optimal set: suppose that it produces A=\{e_1,e_2,\ldots,e_r\} and that B=\{f_1,f_2,\ldots,f_r\}. Now for any k with 1\le k\le r, consider open sets O_1=\{e_1,\ldots,e_{k-1}\} and O_2=\{f_1,\ldots,f_k\}. Since O_1 is smaller than O_2, there is some element of O_2 which can be put into O_1 with the result still being independent. However e_k is an element of maximal weight that can be added to O_1 to maintain independence. Thus e_k is of no smaller weight than some element of O_2, and hence e_k is of at least a large a weight as f_k. As this is true for all k, A is weightier than B.