How do we OPTIMALLY assign drivers to riders? (Hungarian Algorithm) | Bipartite Matchings

How do we optimally match drivers to passengers? Intuitively, we can estimate the waiting time required for a car to reach a passenger, and then find an assignment with the smallest waiting time. This is an example of a bipartite matching problem with edge weights. Here, we want everyone to be matched, while also finding an assignment with the lowest total waiting time.

Finding the optimal matching isn't trivial. The classic algorithm for solving this problem, the Hungarian algorithm, is an example of a primal-dual method, which aims to solve the primal problem (maximum weight matching) by iteratively improving on a dual problem (weighted coverings). To develop the intuition for the Hungarian algorithm, we talk about another problem in graph theory called vertex cover. Vertex covers are an interesting problem in their own right. However, what we need is a generalization of vertex cover to edge-weighted graphs. This generalization of vertex covers to weighted coverings gives us all of the tools necessary to formulate and talk about the Hungarian algorithm.

Also, sorry if the audio seems inconsistent. I was recording over multiple days and I think one day I was slightly sick so my voice was messed up!


Previous video on maximum cardinality matchings:
   • Can we assign everyone a job? (maximum mat...  

Some lecture notes I like:

http://timroughgarden.org/w16/l/l5.pdf
http://www.columbia.edu/~cs2035/cours...


Timestamps:
0:00 Motivation
0:37 Problem Formulation
2:18 Overview of Video
2:54 Vertex Covers & Konig's Theorem
6:14 Generalization of Vertex Cover
11:13 Hungarian Algorithm
16:50 History and Context

Music:

There's Probably No Time by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/...

Source: http://chriszabriskie.com/uvp/

Artist: http://chriszabriskie.com/


John Stockton Slow Drag by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/...

Source: http://chriszabriskie.com/uvp/

Artist: http://chriszabriskie.com/


The Temperature of the Air on the Bow of the Kaleetan by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/...

Source: http://chriszabriskie.com/uvp/

Artist: http://chriszabriskie.com/


The 49th Street Galleria by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/...

Source: http://chriszabriskie.com/uvp/

Artist: http://chriszabriskie.com/