Search Site



Advanced Search


 
Product No. 99781 Supplementary Print Price: FREE with membership
 

Matroids: The Theory and Practice of Greed (UMAP)

Christian Jones


Mathematics Topic:
Computer Science, Graph Theory, Linear Algebra
Application Areas:
Computer science, discrete optimization
Prerequisites:
The reader is assumed to be familiar with elementary concepts in linear algebra (definition and properties of linear independence) and in graph theory (definition of a graph, bipartite graph, and path).

| ©2000 by COMAP, Inc. | The UMAP Journal 21.2 | 23 pages |


This module introduces matroids and demonstrats their application to several discrete optimization problems.

Table of Contents:

INTRODUCTION

MATROIDS

FROM MATROIDS TO GREEDY ALGORITHMS

A SCHEDULING PROBLEM

A TASK ASSIGNMENT PROBLEM

CONCLUSION

EXERCISES

SOLUTIONS TO THE EXERCISES

REFERENCES

ABOUT THE AUTHORS