Return to Colloquia & Seminar listing
Integer Programming and Parameterized Complexity
Optimization| Speaker: | Martin Koutecky, Charles University, Prague |
| Related Webpage: | https://sites.google.com/site/ucdavisoptimization/2016-summer-events-on-research-in-optimization-sero |
| Location: | 2240 MSB |
| Start time: | Fri, Jun 17 2016, 11:00AM |
Parameterized complexity is a subfield of computational complexity which attempts to examine the complexity of a problem more closely in order to identify which aspects (parameters) of an input instance make it computationally easy or hard. For example, in the context of graph problems, structural parameters such as "tree-likeness" or "sparsity" are studied, with many positive results showing that, if a given parameter is kept small, otherwise difficult problems become tractable; hence the name "Fixed Parameter Tractable (FPT) algorithm".
Integer programming in its general form is a notoriously NP-hard problem with wide expressive power. In this talk, we will overview several results which identify parameters of integer programming instances that lead to FPT algorithms. We will also show how to use each of these results to give an FPT algorithm for some problem.
* * *
Martin Koutecky is visiting until Wednesday June 22. If you'd like to meet, contact Matthias Koeppe.