Declawing the conflict graph to approximate intractable matching problems
Abstract
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