Coping with Intractability: Parameterized Algorithms meets Linear Programming

Abstract: This seminar will highlight the role of linear programming techniques in the design of parametrized algorithms as a framework to cope with intractability, which I will attempt to motivate. After a brief introduction, I will also briefly talk about the associated notion of kernelization, which transforms input instances into more “manageable forms”. I will then demonstrate how linear programming is applied in lieu of this framework to obtain a reasonable algorithm from a parametrized complexity perspective for an otherwise intractable problem like vertex cover. Lastly, recent advancements that use similar techniques for vertex cover will also be mentioned. This presentation is part of my graduate coursework on Discrete Optimization.

Mathematics

Audience: researchers in the topic

PIMS-CORDS SFU Operations Research Seminar