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 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