||Wednesday, August 24, 2016
||1:30pm - 2:30pm
||D344 LSRC, Duke
Parameterized algorithms attempt to formally identify special situations where NP-hard problems admit efficient algorithms. Instead of expressing the running time as a function of the input size only, we account for dependence on one or more parameters of the input instance. The hope is that if we achieve a separation of the complexity into a bad dependence (such as exponential) on the parameter but a good (polynomial) dependence on the size of input, then the algorithm may demonstrate reasonable worst-case behavior on classes of inputs where the parameter is guaranteed to be small.
We'll define basic notions like fixed-parameter tractability and kernelization, and explore a few examples of such algorithms in the context of NP-hard problems like Vertex Cover, Satisfiability, and determining a Kemeny winner.
Hosted by: Vince Conitzer