Avoiding the Complexity Cliff in Network Analysis
Blair Sullivan, NC State
Have you ever suddenly realized that every reasonable variant of the problem you're interested in is NP-hard -- dashing your dreams of ever having an efficient algorithm for analyzing that awesome new data set? If not, just wait - it's almost guaranteed to happen (repeatedly) if you work with networks. What if there were an alternative to jumping head-first into the raging river of heuristics? In this talk, we discuss an approach to designing polynomial time algorithms that solve NP-hard problems by exploiting the non-uniformity of algorithmic complexity and inherent structure in the problem instance. We provide a gentle introduction to the main ideas of parameterized complexity, along with several concrete examples of how our group is employing these approaches to solve network analysis problems in computational biology and quantum computing.
November, 21 2016 | 12:45 p.m. - 2:00 p.m. | Gross Hall 230E