The Capacity of Greed

Teena Carroll

Between here and there,
Greedy Ford-Fulkerson 
finds how much to send.

The Science

A graph is a collection of dots (vertices) connected by lines (edges). Edges can be assigned weights (capacities). Picture vertices as cities and each weighed edge recording the volume of cargo that can be shipped directly between a pair of cities. The Ford-Fulkerson algorithm is a set of directions which tells you how to find the maximum flow between two designated vertices on a weighted graph, in other words, the maximum amount of cargo that can be sent from ‘the source’ to ‘the sink’. As long as these vertices have a path between then (i.e, they are connected) the algorithm is guaranteed to find the best solution. The algorithm is greedy-- the ‘locally optimal’ decision is made at every step. Most greedy algorithms have situations where they will find a magnificently poor solution, so it is notable when a greedy algorithm is guaranteed to find the best solution.

The Poet

Teena Carroll is a faculty member at Emory & Henry College in the Appalachian mountains of Virginia, USA. She has studied mathematics at Kenyon College, University of Nebraska- Lincoln and Georgia Institute of Technology. She is working on a Calculus in Haiku project and has contributed to thescikuproject.com. She has been a poet for longer than she has been a mathematician.

Next poem: The Cell Factory by Dayana Hristova