log in  |  register  |  feedback?  |  help  |  web accessibility
Declawing the conflict graph to approximate intractable matching problems
Friday, October 25, 2019, 1:00-2:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

This talk will review why some matching problems are intractable and show how we can use properties of the conflict graph to design approximation algorithms. The motivating example will be a problem based on computing the rearrangement distance between two strings. This is kind of an experimental talk where I’ll try to explain the intuition behind an algorithm and ideas that didn’t make it into the paper.

This talk is organized by Ahmed Abdelkader