Skip to content

Instantly share code, notes, and snippets.

@simplay

simplay/co_10.md

Last active August 29, 2015 14:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save simplay/4052b51db31f2aa25d07 to your computer and use it in GitHub Desktop.
Save simplay/4052b51db31f2aa25d07 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
co_10.md

Find an assignment of the jobs to the machines such that total processing time is minimal.

Given bipartite Graph G = (V,E), determine its minimum weight matching:

1. Relabel edge weight of G: E' = {e' := e and e.w *= -1 | forall e in E}
2. Find minimum edge weight min_e in E'
3. E'' = {e'' := e' and e'.w += min_e | forall e' in E'}
4. Apply maximum weight matching problem to G = (V, E'')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment