What is the distinction between local and greedy algorithms?

464 views Asked by At

I'm creating a simple LPT heuristic algorithm in python in order to solve a timetabling problem.

The LPT algorithm I'm employing is greedy. I'm struggling to understand the distinction between greedy algorithms and local algorithms though. From my understanding a greedy algorithm is an example of a local one. Could anyone elaborate on how local and greedy algorithms sit?

1

There are 1 answers

0
mcdowella On

You should be able to find a reasonably precise definition of Greedy algorithms, because there is a mathematical theory connecting them with Matroids. For instance, https://people.cs.umass.edu/~barring/cs611/lecture/4.pdf first paragraph says "A greedy algorithm tries to solve an optimization problem by always choosing a next step that is locally optimal." and P 10 describes a generic greedy algorithm which produces an optimal set X by sorting candidates and examining candidates in non-increasing order, adding candidates to X when this does not violate the constraints. If there is a Matroid lurking around behind the scenes, the greedy algorithm will return a globally optimal answer.