Parameterized Algorithms
Speaker:  Neeldhara Misra

Date: 
Wednesday, August 24, 2016 
Time: 
1:30pm  2:30pm 
Location: 
D344 LSRC, Duke 


Abstract
Parameterized algorithms attempt to formally identify special situations where NPhard 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 worstcase behavior on classes of inputs where the parameter is guaranteed to be small.
We'll define basic notions like fixedparameter tractability and kernelization, and explore a few examples of such algorithms in the context of NPhard problems like Vertex Cover, Satisfiability, and determining a Kemeny winner.
Hosted by: Vince Conitzer